Submission #979804

#TimeUsernameProblemLanguageResultExecution timeMemory
979804vjudge1Aliens (IOI16_aliens)C++17
100 / 100
207 ms7660 KiB
#include<bits/stdc++.h> //#include "game.h" #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vvi vector<vi> #define vp vector<pii> using namespace std; struct deal{ ll x,y,z; }; long double slope(deal x,deal y){ return ((long double)x.y-y.y)/(y.x-x.x); } pll dp[100005]; vector<pll>pt; pll solve(ll x,int n){ deque<deal>dq;dq.pb({-2*(pt[0].f-1),(pt[0].f-1)*(pt[0].f-1),0}); for(int i=0;i<n;i++){ while(dq.size()>1&&slope(dq[0],dq[1])<pt[i].s)dq.pop_front(); dp[i] = {dq[0].x*pt[i].s+pt[i].s*pt[i].s+dq[0].y+x,dq[0].z+1}; if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s}; while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())>slope(dq.back(),tmp))dq.pop_back(); dq.pb(tmp); }return dp[n-1]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { for(int i=0;i<n;i++){ if(r[i]>c[i])swap(r[i],c[i]); pt.pb({c[i],-r[i]}); }sort(all(pt)); stack<pll>st; for(auto it : pt){ while(!st.empty()&&(st.top().s>=-it.s||st.top().f==it.f))st.pop(); st.push({it.f,-it.s}); }n=st.size();while(!pt.empty())pt.pop_back(); while(!st.empty())pt.pb({st.top().s,st.top().f}),st.pop(); reverse(all(pt));ll le=0,re=1e18; while(le<re){ ll md=(le+re)>>1; if(solve(md,n).s<=k)re=md; else le=md+1; }return solve(le,n).f-le*k; }

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int, int)':
aliens.cpp:27:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |         if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
      |         ^~
aliens.cpp:27:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |         if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
      |                            ^~~~
#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...