Submission #712108

#	Time	Username	Problem	Language	Result	Execution time	Memory
712108		alvingogo	Cake 3 (JOI19_cake3)	C++14	100 / 100	3193 ms	40068 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

vector<pair<int,int> > v;
int n,k;
int ans=-1e18;
vector<pair<int,int> > dp;
struct DS{
	p_q<int,vector<int>,greater<int> > pq,pq2;
	int cnt=0;
	vector<int> v;
	int sum=0;
	void add(int x){
		sum+=x;
		cnt++;
		v.push_back(x);
		pq.push(x);
		if(cnt>k){
			pq2.push(pq.top());
			sum-=pq.top();
			v.push_back({-pq.top()});
			cnt--;
		}
		while(pq.size() && pq2.size() && pq.top()==pq2.top()){
			pq.pop();
			pq2.pop();
		}
	}
	void undo(){
		while(v.back()<0){
			auto h=-v.back();
			v.pop_back();
			pq.push(h);
			cnt++;
			sum+=h;
		}
		pq2.push(v.back());
		sum-=v.back();
		cnt--;
		v.pop_back();
		while(pq.size() && pq2.size() && pq.top()==pq2.top()){
			pq.pop();
			pq2.pop();
		}
	}
	int get(){
		return sum;
	}
}ds;
void dc(int L,int R,int dl,int dr){
	//cal dp[l] to dp[r], where their best transfer point will be in [dl,dr]
	//the (dr,L) is given in ancestor
	if(L>R){
		return;
	}
	//cout << L << " " << R << " " << dl << " " << dr << "\n";
	int m=(L+R)/2;
	for(int i=m;i>=max(L,dr+1);i--){
		ds.add(v[i].fs);	
	}
	for(int i=min(dr,m);i>=dl;i--){
		ds.add(v[i].fs);
		if(m-i+1>=k){
			//cout << ds.get() << " " << v[m].sc-v[i].sc << "\n";
			dp[m]=max(dp[m],{ds.get()-2*(v[m].sc-v[i].sc),i});
		}
	}
	ans=max(ans,dp[m].fs);
	for(int i=min(dr,m);i>=dl;i--){
		ds.undo();
	}
	for(int i=m;i>=max(L,dr+1);i--){
		ds.undo();
	}
	for(int i=dp[m].sc+1;i<=min(L-1,dr);i++){
		ds.add(v[i].fs);
	}
	dc(L,m-1,dl,dp[m].sc);
	for(int i=dp[m].sc+1;i<=min(L-1,dr);i++){
		ds.undo();
	}
	for(int i=max(L,dr+1);i<=m;i++){
		ds.add(v[i].fs);
	}
	dc(m+1,R,dp[m].sc,dr);
	for(int i=max(L,dr+1);i<=m;i++){
		ds.undo();
	}
}
signed main(){
    AquA;
	cin >> n;
	dp.resize(n,{-1e18,-1});
	cin >> k;
	v.resize(n);
	for(int i=0;i<n;i++){
		cin >> v[i].fs >> v[i].sc;
	}
	sort(v.begin(),v.end(),[&](pair<int,int> a,pair<int,int> b){return a.sc<b.sc;});
	for(int i=0;i<n;i++){
		//cout << v[i].fs << " " << v[i].sc << "\n";
	}
	dc(k-1,n-1,0,n-1);
	for(int i=0;i<n;i++){
		//cout << dp[i].fs << " " << dp[i].sc << "\n";
	}
	cout << ans << "\n";
    return 0;
}

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