Submission #105851

#	Time	Username	Problem	Language	Result	Execution time	Memory
105851		Pro_ktmr	Cake 3 (JOI19_cake3)	C++14	0 / 100	5 ms	896 KiB

cake3

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back

int N,M;
pair<LL,LL> CV[200000];

LL dp[2000][2000];
LL solve(int now, int nokori){ //now wo eranda
	if(nokori == 0) return 0;
	if(dp[now][nokori] != LLONG_MAX) return dp[now][nokori];
	LL ans = LLONG_MIN;
	for(int i=now+1; i<=N-nokori; i++){
		ans = max(ans, CV[i].second-(CV[i].first-CV[now].first)*2+solve(i, nokori-1));
	}
	return dp[now][nokori] = ans;
}

LL answer(){
	LL ans = LLONG_MIN;
	for(int i=0; i<=N-M; i++){
		ans = max(ans, CV[i].second+solve(i, M-1));
	}
	return ans;
}

int main(){
	cin >> N >> M;
	if(N > 2000) return -1;
	for(int i=0; i<N; i++){
		cin >> CV[i].second >> CV[i].first;
		for(int j=0; j<N; j++) dp[i][j] = LLONG_MAX;
	}
	sort(CV, CV+N);
	
	cout << answer() << endl;
	
	for(int i=0; i<N; i++){
		if(i <= N-M) cout << CV[i].second+solve(i, M-1) << "\t";
		else cout << "\t";
		for(int j=M; j>=0; j--){
			if(i >= N-j){
				cout << "\t";
				continue;
			}
			cout << solve(i, j) << "\t";
		}
		cout << endl;		
	}
	
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76