• API
• FAQ
• Tools
• Archive
daily pastebin goal
50%
SHARE
TWEET

a guest Apr 15th, 2018 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. const int N = 55;
6. const long long INF = 1e18;
7.
8. int n, m, q;
9. int a[N], b[N], p[N];
10. int x[N], y[N];
11. long long f[N][N][N][N];
12.
13. long long solve(int t, int l, int r, int lim) {
14.     long long &ret = f[t][l][r][lim];
15.     if (ret != -1) return ret;
16.     if (l > r) return ret = 0;
17.     ret = INF;
18.     int p = 0;
19.     for (int i = l; i <= r; ++i) {
20.         if (b[i] >= lim) continue;
21.         if (!p || b[i] > b[p]) p = i;
22.     }
23.     if (t) {
24.         ret = min(ret, solve(t - 1, l, r, b[p]));
25.     }
26.     if (!p) return ret = 0;
27.     long long cost = 0;
28.     for (int i = 1; i <= q; ++i) {
29.         if (x[i] >= l && y[i] <= r && x[i] <= p && p <= y[i]) cost += a[p];
30.     }
31.     for (int i = 0; i <= t; ++i) {
32.         ret = min(ret, solve(i, l, p - 1, b[p]) + solve(t - i, p + 1, r, b[p]) + cost);
33.     }
34.     return ret;
35. }
36.
37. int main() {
38.     ios::sync_with_stdio(false);
39.     cin >> n >> m >> q;
40.     for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = i;
41.     sort(p + 1, p + 1 + n, [&] (int x, int y) {
42.         return a[x] < a[y];
43.     });
44.     for (int i = 1; i <= n; ++i) b[p[i]] = i;
45.     for (int i = 1; i <= q; ++i) {
46.         cin >> x[i] >> y[i];
47.     }
48.     memset(f, -1, sizeof f);
49.     cout << solve(m, 1, n, n + 1);
50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top