제출 #331274

#제출 시각아이디문제언어결과실행 시간메모리
331274EIMONIMCake 3 (JOI19_cake3)C++14
100 / 100
1399 ms18536 KiB
#include <bits/stdc++.h> #define int int64_t #define vi vector<int> #define ii pair<int,int> #define vb vector<bool> #define vvi vector<vi> #define vvb vector<vb> #define vii vector<ii> #define vvii vector<vii> #define x first #define y second #define pb push_back #define loop(i,s,e) for(int i=s;i<e;i++) #define loopr(i,s,e) for(int i=e-1;i>=s;i--) #define chkmax(a,b) a = max(a,b) #define chkmin(a,b) a=min(a,b) #define all(x) x.begin(),x.end() using namespace std; const int INF = 1e18, MOD = 1e9 + 7; const int MAXN = 2e5+10; struct Seg{ int sz; vi a, amt, v; void init(int n){ for(sz=1;sz<n;sz*=2); a.resize(2*sz); amt.resize(2*sz); } void update(int i, bool b){ i+=sz; amt[i] = b; a[i] = v[i-sz] * b; for(i/=2; i; i/=2) a[i] = a[2*i] + a[2*i+1], amt[i] = amt[2*i] + amt[2*i+1]; } int query(int k){ if (amt[1]<k) return -INF; int res = 0, i = 1; for(; i<sz; ){ //cout<<"AMT: "<<i<<" : "<<k<<" "<<amt[i]<<" "<<amt[2*i]<<" "<<amt[2*i+1]<<endl; if (amt[2*i]<=k) k-=amt[2*i], res+=a[2*i], i = 2*i+1; else i = 2*i; } if (k) res+=a[i], k--; //cout<<"K: "<<k<<endl; assert(k==0); return res; } } seg; int n,m; ii a[MAXN]; int ll=0,rr=-1; int res = 0; int back[MAXN]; void update(int aa, int bb){ if (aa > rr || bb < ll){ while(ll<=rr) seg.update(back[ll++], 0); ll = aa, rr = aa-1; } while(bb>rr) seg.update(back[++rr],1); while(aa<ll) seg.update(back[--ll],1); while(bb<rr) seg.update(back[rr--],0); while(aa>ll) seg.update(back[ll++],0); } int ans = -INF; void solve(int l, int r, int optl, int optr){ if (r<l) return ; int i = (l+r)/2; if (optr - i+1 < m){ // cant do i solve(l, i-1, optl, optr); return ; } int opt = optr, bestv = -INF/2; loop(j,optl,optr+1){ if (j-i+1 < m) continue; update(i, j); int v = seg.query(m) - (a[j].x - a[i].x); if (bestv < v){ bestv = v; opt = j; } } chkmax(ans, bestv); solve(i+1, r, opt, optr); solve(l, i-1, optl, opt); } int32_t main(){ ios_base::sync_with_stdio(false); cin>>n>>m; vii vals(n); loop(i,0,n) cin>>a[i].y>>a[i].x, a[i].x*=2; sort(a, a+n); loop(i,0,n) vals[i] = {a[i].y, i}; sort(all(vals)); reverse(all(vals)); seg.init(n); loop(i,0,n) seg.v.pb(vals[i].x), back[vals[i].y] = i; solve(0,n-m,m-1,n-1); cout<<ans<<endl; return 0; } /* color a cls g++ cake3.cpp -o a & a 5 3 2 1 4 2 6 4 8 8 10 16 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...