Seletiva IOI 2013

pagamento.cpp

// Ivan Carvalho
// Pagamento - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
using namespace std;
#define MAXN 4001
typedef long long ll;
const ll INF = 1e15;
ll soma[MAXN][MAXN];
ll C[MAXN];
ll F[MAXN][MAXN];
ll salario;
int N,K;
int P[MAXN][MAXN];
void precalcula(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=i;j++){
			soma[i][j] = soma[i][j-1] + (C[i] - C[j]);
		}
	}
}
inline ll custo(int i,int j){
	if(i > j) return 0;
	//printf("Custo %d %d: %lld\n",i,j,soma[j][j] - soma[j][i-1]);
	return soma[j][j] - soma[j][i-1];
}
void solve(int k,int l1,int l2,int p1,int p2){
	if(l1 > l2) return;
	int lm = (l1+l2)/2;
	P[k][lm] = -1;
	F[k][lm] = INF;
	for(int g=p1;g<=min(p2,lm-1);g++){
		ll novo_custo = F[k-1][g] + custo(g+1,lm);
		if(novo_custo < F[k][lm]){
			F[k][lm] = novo_custo;
			P[k][lm] = g;
		}
	}
	solve(k,l1,lm-1,p1,P[k][lm]);
	solve(k,lm+1,l2,P[k][lm],p2);
}
int main(){
	scanf("%d %d",&N,&K);
	for(int i=1;i<=N;i++){
		ll ci,di,vi;
		scanf("%lld %lld %lld",&ci,&di,&vi);
		salario += ci;
		C[i] = di/vi;
		//printf("%lld\n",C[i]);
	}
	sort(C+1,C+N+1);
	precalcula();
	for(int l=1;l<=N;l++){
		F[1][l] = custo(1,l);
		P[1][l] = 0;
	}
	for(int k=2;k<=K;k++){
		solve(k,0,N,0,N);
	}
	printf("%lld\n",salario + F[K][N]);
	return 0;
}