제출 #948271

#제출 시각아이디문제언어결과실행 시간메모리
948271pccCake 3 (JOI19_cake3)C++17
0 / 100
26 ms145284 KiB
#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]; 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,ql); for(int i = opl;i<=min(mid-M,opr);i++){ auto tmp = calc(i,mid); if(tmp>=val)val = tmp,opt = i; } 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); }

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...