oj.uz

Submission #105851

# Submission time Handle Problem Language Result Execution time Memory
105851 2019-04-15T10:39:54 Z Pro_ktmr Cake 3 (JOI19_cake3) C++14
0 / 100
 5 ms 896 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 76.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -