제출 #890570

#제출 시각아이디문제언어결과실행 시간메모리
890570ASN49KAliens (IOI16_aliens)C++14
4 / 100
2076 ms444 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) { assert(c.a!=d.a); 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) { 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++; if(i!=n-1)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=INF; for(int i=0;i<=dr;i++) { auto sol=aliens(a,n,i); if(sol.second<=k) { rez=min(rez,sol.first-i*sol.second); } } return rez; }

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

aliens.cpp: In function 'i64 take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:116:9: warning: unused variable 'st' [-Wunused-variable]
  116 |     i64 st=0,dr=1LL*m*m;
      |         ^~
#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...