제출 #938025

#제출 시각아이디문제언어결과실행 시간메모리
938025DobromirAngelovAliens (IOI16_aliens)C++14
100 / 100
214 ms8900 KiB
#include "aliens.h" #include<bits/stdc++.h> #define fi first #define se second using namespace std; const int MAXN=1e5+5; const long long INF=1e18; struct Line { long long k,n; long long st; int num; Line() {}; Line(long long _k,long long _n,long long _st,int _num) { k=_k; n=_n; st=_st; num=_num; } }; int n,m,k; pair<int,int> tmp[MAXN]; vector<pair<long long,long long> > a; long long dp[MAXN]; int seg[MAXN]; Line lines[MAXN]; int beg=0, en=-1; long long crossX(Line a,Line b) { long long diffK=a.k-b.k; long long diffN=b.n-a.n; if(diffK==0) { if(a.n>b.n) return INF; else return 0; } return (diffN+diffK-1)/diffK; } void addLine(Line cur) { while(en-beg+1>0 && crossX(lines[en], cur)<=lines[en].st) en--; if(en-beg+1>0) cur.st=crossX(lines[en], cur); lines[++en]=cur; } pair<int,long long> query(long long x) { while(en-beg+1>1 && lines[beg+1].st<=x) beg++; return {lines[beg].num, lines[beg].k*x+lines[beg].n}; } void resetLines() { beg=0; en=-1; } int solve(long long pen) { resetLines(); dp[0]=0; seg[0]=0; for(int i=1; i<=n; i++) { long long x=a[i].fi; long long t=max(0LL, a[i-1].se-x+1); addLine(Line(-(x-1)*2, (x-1)*(x-1)-t*t+dp[i-1]+pen, 0, i)); pair<int,long long> qr=query(a[i].se); dp[i]=qr.se+a[i].se*a[i].se; seg[i]=seg[qr.fi-1]+1; } return seg[n]; } long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c) { n=_n; m=_m; k=_k; for(int i=0; i<n; i++) { _r[i]++; _c[i]++; if(_r[i]>_c[i]) swap(_r[i], _c[i]); tmp[i+1].fi=_r[i], tmp[i+1].se=_c[i]; } sort(tmp+1,tmp+n+1,[](pair<long long,long long> x,pair<long long,long long> y) { if(x.fi==y.fi) return x.se>y.se; return x.fi<y.fi; }); a.push_back({0,0}); for(int i=1; i<=n; i++) { if(tmp[i].fi>a.back().fi && tmp[i].se>a.back().se) a.push_back(tmp[i]); } n=a.size()-1; k=min(k,n); long long l=0,r=1e18; while(l<r) { long long mid=(l+r+1)/2; if(solve(mid)>=k) l=mid; else r=mid-1; } solve(l); long long ans=dp[n]-k*l; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...