Skip to content

Instantly share code, notes, and snippets.

@asi1024
Created Aug 29, 2015
Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment