Submission #948274

#	Time	Username	Problem	Language	Result	Execution time	Memory
948274		pcc	Cake 3 (JOI19_cake3)	C++17	100 / 100	761 ms	150472 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
vector<int> all;

struct node{
	int pl,pr,cnt;
	ll sum;
	node(){
		pl = pr = cnt = sum = 0;
	}
};
const int SZ = mxn*30;
node seg[SZ];
int ppp = 0;

int newnode(int src){
	ppp++;
	assert(ppp<SZ);
	seg[ppp] = seg[src];
	return ppp;
}

#define mid ((l+r)>>1)
int modify(int now,int l,int r,int p,int v){
	now = newnode(now);
	if(l == r){
		seg[now].cnt++;
		seg[now].sum += v;
		return now;
	}
	if(mid>=p)seg[now].pl = modify(seg[now].pl,l,mid,p,v);
	else seg[now].pr = modify(seg[now].pr,mid+1,r,p,v);
	seg[now].sum = seg[seg[now].pl].sum+seg[seg[now].pr].sum;
	seg[now].cnt = seg[seg[now].pl].cnt+seg[seg[now].pr].cnt;
	return now;
}
ll getval(int s,int e,int l,int r,int tar){
	if(l == r){
		return 1ll*all[l]*min(seg[e].cnt-seg[s].cnt,tar);
	}
	if(seg[seg[e].pr].cnt-seg[seg[s].pr].cnt>=tar)return getval(seg[s].pr,seg[e].pr,mid+1,r,tar);
	else return getval(seg[s].pl,seg[e].pl,l,mid,tar-(seg[seg[e].pr].cnt-seg[seg[s].pr].cnt))+seg[seg[e].pr].sum-seg[seg[s].pr].sum;
}
#undef mid

int rt[mxn];
pii arr[mxn];
int N,M;
ll ans[mxn];
int cut[mxn];

ll calc(int a,int b){
	auto re = getval(rt[a],rt[b],0,all.size(),M)+arr[a+1].fs*2-arr[b].fs*2;
	return re;
}

void dc(int ql,int qr,int opl,int opr){
	int mid = (ql+qr)>>1;
	int opt = opl;
	ll val = calc(opl,mid);
	for(int i = opl;i<=min(mid-M,opr);i++){
		auto tmp = calc(i,mid);
		if(tmp>=val){
			val = tmp;
			opt = i;
		}
	}
	cut[mid] = opt;
	ans[mid] = val;
	if(ql != mid)dc(ql,mid-1,opl,opt);
	if(qr != mid)dc(mid+1,qr,opt,opr);
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(auto &i:ans)i = -1e18;
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].sc>>arr[i].fs;
		all.push_back(arr[i].sc);
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	sort(arr+1,arr+N+1);
	for(int i = 1;i<=N;i++){
		arr[i].sc = lower_bound(all.begin(),all.end(),arr[i].sc)-all.begin();
		rt[i] = modify(rt[i-1],0,all.size(),arr[i].sc,all[arr[i].sc]);
	}
	//cout<<seg[rt[N]].sum<<":"<<seg[rt[N]].cnt<<' '<<getval(rt[0],rt[3],0,all.size(),M)<<endl;
	dc(M,N,0,N);
	cout<<*max_element(ans+M,ans+N+1);
}
/*
27 11
174927229 175619520
659438138 203046830
272874664 929919327
926160879 187350846
559024721 662907414
894248432 240671032
511729366 318988755
559435835 14805298
639217114 698393694
17305812 411948960
166964019 123825591
184275720 423632616
118247433 293047457
918915605 91935630
329234641 266319241
552795369 846204607
321833012 304909419
509527412 423225897
59486106 45139906
325406721 409293214
853688573 918521698
700793721 329253453
444542680 179650098
780637054 561404768
63045237 829861193
291909473 963758900
570230725 201755261
*/

Compilation message (stderr)

cake3.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

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