제출 #768143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768143		minhcool	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	340 KiB

cake3

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int n, m, v[N], c[N];

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ii dp[N][3];

ii maxi(ii a, ii b){
	if(a.fi != b.fi) return (a.fi > b.fi ? a : b);
	else return (a.se < b.se ? a : b);
}

ii cal(int ronaldo){
	for(int i = 0; i <= n; i++){
		for(int j = 0; j < 3; j++) dp[i][j] = {-oo, -oo};
	}
	dp[0][0] = {0, 0};
	for(int i = 1; i <= n; i++){
		dp[i][0] = {0, 0};
		dp[i][1] = maxi({dp[i - 1][0].fi + v[i] + 2 * c[i] - ronaldo, dp[i - 1][0].se + 1}, {dp[i - 1][1].fi + v[i] - ronaldo, dp[i - 1][1].se + 1});
		dp[i][1] = maxi(dp[i][1], dp[i - 1][1]);
		dp[i][2] = maxi({dp[i - 1][1].fi + v[i] - 2 * c[i] - ronaldo, dp[i - 1][1].se + 1}, dp[i - 1][2]);
	}
	return dp[n][2];
}

ii arr[N];

bool cmp(ii a, ii b){
	return a.se < b.se;
}

#ifdef local
void process(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> c[i];
	for(int i = 1; i <= n; i++) arr[i] = {v[i], c[i]};
	sort(arr + 1, arr + n + 1, cmp);
	for(int i = 1; i <= n; i++){
		v[i] = arr[i].fi;
		c[i] = arr[i].se;
	}
	int le = -2e12, ri = 2e12;
	int answer = -oo;
	while(le < ri - 2){
		int mid = (le + ri) >> 1;
		ii temp = cal(mid);
		if(temp.se >= m) le = mid;
		else ri = mid;
	//	cout << le << " " << ri << " " << temp.fi << " " << temp.se << "\n";
	//	if(temp.se <= m) answer = max(answer, temp.fi - m * temp.se);
	}
	for(int i = le; i <= ri; i++){
		ii temp = cal(i), temp2 = cal(i - 1);
	//	cout << i << " " << temp.fi << " " << temp.se << " " << temp2.fi << " " << temp2.se << "\n";
		if(temp.se <= m &&  temp2.se >= m) answer = max(answer, temp.fi + (temp.se) * i);
	}
	cout << answer << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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