Submission #1051541

#TimeUsernameProblemLanguageResultExecution timeMemory
1051541ReLiceAliens (IOI16_aliens)C++17
4 / 100
14 ms125960 KiB
#include "aliens.h" #include <bits/stdc++.h> #define ll int #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=4e3+5; struct Line{ ll m,b; ll operator () (ll x){return m * x + b;} bool ok(Line x, Line y){ ll t1 = (b - x.b); ll b1 = (x.m - m); ll t2 = (x.b - y.b); ll b2 = (y.m - x.m); return t1 * b2 <= t2 * b1; } }; ll sq(ll x){ return x*x; } long long dp[N][N]; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { ll i,q; vll len,nxt; {//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); } c.clear(); c.pb(0); for(i=1;i<=n;i++){ nxt.pb(r[i] - len[i]); c.pb(nxt.bc); len[i - 1] = r[i - 1] - nxt[i - 1] ; len[i - 1] = max(len[i - 1], 0); } len[0]=0; nxt.pb(r[n]); memset(dp, 0x3f, sizeof(dp)); for(i=0;i<=k;i++) dp[0][i] = 0; vector<deque<Line>> ch(k+5); for(i=0;i<=n;i++){ for(q=1;q<=k;q++){ //~ if(dp[i][q] >= dp[N - 1][N - 1]) continue; auto &dq = ch[q-1]; ll x = r[i]; while(dq.sz > 1 && dq[0](x) > dq[1](x)){ dq.pof; } if(i>0){ dp[i][q] = r[i] * r[i] + dq[0](x); //~ cout<<dq[0].m<<' '<<dq[0].b<<endl; //~ cout<<i<<' '<<q<<endl; //~ cout<<dp[i][q]<<endl; } ll m = (-2) * nxt[i]; ll b = nxt[i] * nxt[i] - len[i] * len[i] + dp[i][q]; Line cur = {m, b}; //~ cout<<i<<' '<<q<<endl; //~ cout<<m<<' '<<b<<endl; while((ll) dq.sz > 2 && dq[dq.sz - 2].ok(dq.bc, cur)) dq.pob; dq.pb(cur); //~ dp[i][q] = r[i]*r[i] - 2 * r[i] * nxt[j] + nxt[j] * nxt[j] - len[j] * len[j] + dp[j][q - 1]; //~ for(j=0;j<i;j++){ //~ dp[i][q] = min(dp[i][q], dp[j][q - 1] + sq(r[i] - nxt[j]) - sq(len[j])); //~ } } } long long ans=dp[n+1][0]; for(i=0;i<=k;i++) ans=min(ans,dp[n][i]); return ans; }
#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...