제출 #1056672

#제출 시각아이디문제언어결과실행 시간메모리
1056672ReLiceAliens (IOI16_aliens)C++17
100 / 100
204 ms15156 KiB
#include "aliens.h" #include <bits/stdc++.h> #define ll long long #define sz size() #define all(x) x.begin(),x.end() #define vll vector<ll> #define str string #define pb push_back #define pof pop_front() #define pf push_front #define pob pop_back() #define bc back() using namespace std; const ll N=1e5+5; const ll inf = 1e18; struct Line{ ll m, b, c; Line(ll m = 0, ll b = 0, ll c = 0) : m(m), b(b), c(c) {} ll operator () (ll x){return m * x + b;} bool ok(Line x, Line y){ ll t1 = (x.b - b); ll b1 = (m - x.m); ll t2 = (y.b - b); ll b2 = (m - y.m); return t1 * b2 >= t2 * b1; } }; ll sq(ll x){ return x*x; } long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) { ll i; ll n=N,m=M,k=K; vll len, nxt; vll c, r; for(auto i : C)c.pb(i); for(auto i : R)r.pb(i); {//deleting unnecessary ones vll mx(m, m), nr; for(i=0;i<n;i++){ if(r[i] < c[i]) swap(r[i], c[i]); mx[r[i]] = min(mx[r[i]], c[i]); } for(i=m-1;i>=0;i--){ if(mx[i] > i)continue; if(nr.empty() || mx[nr.bc] > mx[i]){ nr.pb(i); len.pb(i-mx[i]+1); } } nr.pb(-1), len.pb(-1);//changing indexation reverse(all(nr)); reverse(all(len)); r=nr; n=r.size()-1; k = min(k, n); } {//redeclaring and recalculating stuff c.clear(); c.pb(0); for(i=1;i<=n;i++){ nxt.pb(r[i] - len[i]); c.pb(nxt.bc + 1); len[i - 1] = r[i - 1] - nxt[i - 1] ; len[i - 1] = max(len[i - 1], 0ll); } len[0]=0; nxt.pb(r[n]); } ll ans; auto calc = [&](ll lm){ vll dp(n + 1, inf); dp[0]=0; deque<Line> dq; vll c(n + 1, 0); for(i=1;i<=n;i++){ ll x = r[i]; while((ll)dq.sz > 1 && (dq[0](x) > dq[1](x) || (dq[0](x) > dq[1](x) && dq[0].c >= dq[1].c)) ){ dq.pof; } if(dq.sz){ dp[i] = sq(r[i]) + dq[0](x) + lm; c[i] = dq[0].c + 1; //~ if(lm == 4){ //~ cout<<dp[i]<<endl; //~ cout<<dq[0].m<<' '<<dq[0].b<<endl; //~ } } if(dp[i] >= sq(r[i] - nxt[0]) + lm){ dp[i] = sq(r[i] - nxt[0]) + lm; c[i] = 1; } ll m = (-2) * nxt[i]; ll b = nxt[i] * nxt[i] - len[i] * len[i] + dp[i]; Line cur = {m, b, c[i]}; while((ll) dq.sz > 1 && dq[dq.sz - 2].ok(dq.bc, cur)) dq.pob; dq.pb(cur); } //~ if(lm == 4){ //~ for(i=1;i<=n;i++){ //~ cout<<dp[i]<<' '<<c[i]<<endl; //~ } //~ } ans = dp[n]; return c[n]; }; { ll l = 0; ll r = inf; while(l + 1 < r){ ll m = (l + r) / 2; if(calc(m) <= k) r = m; else l = m; } calc(r); //~ cout<<calc(r)<<' '<<r<<' '<<ans<<endl; return ans - k * r; } }
#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...