Submission #233057

#	Time	Username	Problem	Language	Result	Execution time	Memory
233057		oolimry	Cake 3 (JOI19_cake3)	C++14	0 / 100	6 ms	2688 KiB

cake3

#include <bits/stdc++.h>
#define C first
#define V second
using namespace std;
typedef pair<long long, long long> ii;

int n, m; 

long long op[300005];
ii arr[200005];

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m; m -= 2;
	
	for(int i = 1;i <= n;i++) cin >> arr[i].V >> arr[i].C;
	sort(arr+1,arr+n+1);
	
	long long ans = -1e18;
	
	fill(op,op+300004, n); op[0] = 1; 
	for(int bit = (1<<17);bit >= 1;bit >>= 1){
		for(int s = bit;s < n - m;s += 2*bit){
			int L, R;
			L = op[s-bit];
			R = op[s+bit];
			L = max(s+1, L);
			
			long long bestValue = -1e18;
			long long bestPos = -1;
			
			priority_queue<long long, vector<long long>, greater<long long> > pq;
			long long acc = 0;
			for(int e = L;e <= R;e++){
				if((int) pq.size() >= m){
					if((int) pq.size() > m){
						acc -= pq.top();
						pq.pop();
					}
					long long val = acc + arr[s].V + arr[e].V - 2*arr[e].C + 2*arr[s].C;
					ans = max(ans, val);
					if(bestValue < val){
						bestValue = val;
						bestPos = e;
					}
				}
				
				pq.push(arr[e].V);
				acc += arr[e].V;
			}
			
			op[s] = bestPos;
		}
	}
	
	cout << ans;	
}

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