제출 #285832

#제출 시각아이디문제언어결과실행 시간메모리
285832eohomegrownappsAliens (IOI16_aliens)C++14
60 / 100
1694 ms1048576 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; ll INF = 1e18; struct Line{ ll m = 0; ll c = INF; Line(ll _m, ll _c){ m=_m; c=_c; } ll f(ll x){ return m*x + c; } ld intersectX(Line &a){ return (1.0*(a.c-c))/(m-a.m); } }; struct ConvexHull{ deque<Line> dq; void insert(Line l){ // wlog gradients decreasing if (dq.size()==0){ dq.push_back(l); return; } if (dq.back().m == l.m){ if (l.c < dq.back().c){ dq.pop_back(); dq.push_back(l); } return; } int s = dq.size(); while (s>=2 && l.intersectX(dq[s-1])<l.intersectX(dq[s-2])){ dq.pop_back(); s--; } dq.push_back(l); } ll query(ll x){ while (dq.size()>=2 && dq[0].f(x)>dq[1].f(x)){ dq.pop_front(); } return dq[0].f(x); } }; long long take_photos(int n, int m, int k, std::vector<int> rv, std::vector<int> cv) { vector<pair<ll,ll>> ptmp(n); for (int i = 0; i<n; i++){ if (cv[i]>rv[i]){ ptmp[i]={rv[i],-cv[i]}; } else { ptmp[i]={cv[i],-rv[i]}; } } sort(ptmp.begin(),ptmp.end()); vector<ll> r; vector<ll> c; c.push_back(ptmp[0].first); r.push_back(-ptmp[0].second); for (int i = 1; i<n; i++){ if (c.back()<ptmp[i].first&&-r.back()>ptmp[i].second){ c.push_back(ptmp[i].first); r.push_back(-ptmp[i].second); } } /*cout<<"points (monotonically decreasing):\n"; for (int i = 0; i<c.size(); i++){ cout<<c[i]<<' '<<r[i]<<'\n'; }*/ n = c.size(); vector<ll> intersect(n-1); for (int i = 0; i<n-1; i++){ ll b = r[i]; ll a = c[i+1]; if (b<a){ continue; } //cout<<"intersect "<<a<<' '<<b<<'\n'; intersect[i] = (b-a+1) * (b-a+1); } /*cout<<"intersect values:\n"; for (int i : intersect){ cout<<i<<' '; }cout<<'\n';*/ vector<vector<ll>> dp(k+1,vector<ll>(n,INF)); ll minans = INF; for (int num = 1; num<=k; num++){ ConvexHull hull; hull.insert({2-2*c[0],(c[0]-1)*(c[0]-1)}); for (int x = 0; x<n; x++){ dp[num][x] = r[x]*r[x] + hull.query(r[x]); if (x!=n-1){ hull.insert({2-2*c[x+1], dp[num-1][x]-intersect[x]+(c[x+1]-1)*(c[x+1]-1)}); } else { minans=min(minans,dp[num][x]); } } } /*for (int num = 1; num<=k; num++){ for (int x = 0; x<n; x++){ cout<<dp[num][x]<<' '; }cout<<'\n'; }*/ return minans; }
#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...