Submission #890547

#TimeUsernameProblemLanguageResultExecution timeMemory
890547ASN49KAliens (IOI16_aliens)C++14
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; using i64=long long; const i64 INF=1e18; #define bug(x) cerr<<#x<<x<<'\n'; #define all(yy) yy.begin(),yy.end() #define pb push_back const int inf=1e9; struct duo { int l,r; bool operator <(const duo&b)const { if(l==b.l) { return r>b.r; } return l<b.l; } }; ////////////////////////////GEOMETRY //////////////////////////////////// struct line { i64 a,b; i64 calculate(int x) { return a*x+b; } }; struct node { line a; int k; }; i64 intersect(const line& c,const line& d) { return (d.b-c.b+c.a-d.a-1)/(c.a-d.a); } struct CHT { deque<node>d; void add(const node e) { while(d.size()>=2) { i64 i1=intersect(d[d.size()-2].a,d.back().a); i64 i2=intersect(d.back().a,e.a); if(i1>i2 || (i1==i2 && d.back().k>e.k)) { d.pop_back(); } else { break; } } d.pb(e); } pair<i64,int> query(int val) { while(d.size()>=2 && d[0].a.calculate(val)>=d[1].a.calculate(val)) { d.pop_front(); } return {d[0].a.calculate(val),d[0].k}; } void clear() { d.clear(); } }; i64 pow2(i64 x) { return x*x; } ///////////////////////////////////////////////////// ///////////////////////////////////////////////////// pair<i64,int> aliens(vector<duo>&a,int n,i64 cost_extra) { CHT cht; cht.add({{-2*(a[0].l-1),pow2(a[0].l-1)},0}); pair<i64,int>sol; for(int i=0;i<n;i++) { sol=cht.query(a[i].r); sol.first+=pow2(a[i].r)+cost_extra; sol.second++; cht.add({{-2*(a[i+1].l-1) , pow2(a[i+1].l-1)-pow2(max(0,a[i].r-a[i+1].l+1))+sol.first},sol.second}); } return sol; } i64 take_photos(int n, int m, int k, vector<int> rr, vector<int> cc) { vector<duo>a(n); for(int i=0;i<n;i++) { a[i]={min(rr[i],cc[i]),max(rr[i],cc[i])}; } vector<duo>aux=a; a.clear(); sort(all(aux)); int maxx=-1; for(auto &c:aux) { if(c.r>maxx) { a.pb(c); maxx=c.r; } } aux.clear(); n=(int)a.size(); i64 st=0,dr=1LL*m*m; i64 rez=-1; while(st<=dr) { i64 m=(st+dr)/2; auto sol=aliens(a,n,m); if(k>=sol.second) { dr=m-1; rez=sol.first-m*sol.second; } else { st=m+1; } } return rez; }
#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...