Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define REP(i,n) for(int i=0;i<(int)(n);i++)
- #define ALL(x) (x).begin(),(x).end()
- using namespace std;
- typedef long long ll;
- const ll INF = 1e14;
- int S, N, M;
- ll P[2048], sum[2048];
- pair<ll,int> memo[2048][2048];
- ll range(int i, int j) { return P[j] * (j - i) - sum[j] + sum[i]; }
- pair<ll,int> dp(int n, int m) {
- if (m == -1) return make_pair(INF, 0);
- if (n <= m) return make_pair(0, n-1);
- if (memo[n][m].first != -1) return memo[n][m];
- pair<ll,int> res = make_pair(INF, 0);
- int from = dp(n-1, m).second, to = dp(n, m+1).second;
- for (int i = from; i <= min(n-1, to); ++i)
- res = min(res, make_pair(dp(i, m-1).first + range(i, n-1), i));
- return memo[n][m] = res;
- }
- int main() {
- cin >> S >> N >> M;
- vector<int> x(S);
- REP(i,S) cin >> x[i];
- REP(i,N) {
- int t, p; cin >> t >> p;
- P[i] = t - x[p-1];
- }
- sort(P, P+N);
- REP(i,N) sum[i+1] = sum[i] + P[i];
- memset(memo, -1, sizeof(memo));
- cout << dp(N, M).first << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement