Submission #1088786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088786		coldbr3w	Cake 3 (JOI19_cake3)	C++17	24 / 100	138 ms	78672 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll blocks = 350;
ll n,m;
pll a[N];
ll dp[2024][2024];
void to_thic_cau(){
	cin >> n >> m;
	for(int i = 1; i <= n;i++) cin >> a[i].F >> a[i].S;
	sort(a + 1, a + n + 1, [&](const pll &a, const pll &b){
		return a.S < b.S;
	});
	for(int i = 0; i <= n;i++){
		for(int j = 0; j <= m;j++) dp[i][j] = -inf;
	}
	for(int i = 1; i <= n;i++){
		for(int j = 1; j <= m;j++){
			if(j == 1) dp[i][j] = max(dp[i-1][j], a[i].F + 2 * a[i].S);
			else if(j == m) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + a[i].F - 2 * a[i].S);
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + a[i].F);
		}
	}
	cout << dp[n][m] << '\n';
}

signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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