제출 #1277605

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

cake3

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,m,ll = 1,rr = 0,ans = 0;
pii st[4*N],a[N];
vector<int>nen;
bool cmp(pii a, pii b){
	return a.se < b.se;
}
pii merge(pii a, pii b){
	return {a.fi+b.fi,a.se+b.se};
}
void update(int id, int l, int r, int i, int val){
	if(l > i || r < i) return;
	if(l == r){
		st[id].fi += val*nen[l-1];
		st[id].se += val;
		return;
	}
	int mid = (l+r)/2;
	update(2*id,l,mid,i,val);
    update(2*id+1,mid+1,r,i,val);
    st[id] = merge(st[2*id],st[2*id+1]);
}
int get(int id, int l, int r, int k){
	if(k == 0) return 0;
	if(l == r){
		return k*nen[l-1];
	}
	int mid = (l+r)/2;
	if(k >= st[2*id+1].se) return st[2*id+1].fi+get(2*id,l,mid,k-st[2*id+1].se);
	return get(2*id+1,mid+1,r,k);
}
void chimto(int l1, int r1){
	while(ll < l1){ 
	    update(1,1,nen.size(),a[ll].fi,-1); 
		ll++; 
	}
    while(ll > l1){ 
	    ll--; 
		update(1,1,nen.size(),a[ll].fi,1); 
	}
    while(rr < r1){ 
	    rr++; 
		update(1,1,nen.size(),a[rr].fi,1); 
	}
    while(rr > r1){ 
	    update(1,1,nen.size(),a[rr].fi,-1); 
		rr--; 
	}
}
void dnc(int l, int r, int x, int y){
    if(l > r) return;
    int mid = (l+r)/2;
    int opt;
    int mx = -1;
    int lim = min(mid-m+1,y);
    for(int i = x; i <= lim; i++){
    	chimto(i+1,mid-1);
    	int val = nen[a[mid].fi-1]+nen[a[i].fi-1]+get(1,1,nen.size(),m-2)-2*(a[mid].se-a[i].se);
        if(val > mx){
            mx = val;
            opt = i;
        }
    }
    ans = max(ans,mx);
    dnc(l,mid-1,x,opt);
    dnc(mid+1,r,opt,y);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    sort(a+1,a+n+1,cmp);
    for(int i = 1; i <= n; i++) nen.push_back(a[i].fi);
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    for(int i = 1; i <= n; i++) a[i].fi = lower_bound(nen.begin(),nen.end(),a[i].fi)-nen.begin()+1;
    dnc(1,n,1,n);
    cout << ans;
}

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