Submission #1274403

#TimeUsernameProblemLanguageResultExecution timeMemory
1274403scalifrastico_098Aliens (IOI16_aliens)C++20
0 / 100
1 ms336 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; int n1, k1; vector<long long> lr, rr; struct l { long long m, b, f; }; struct ch { deque<l>dq; long long ev(const l& li, long long x){return li.m*x+li.b;} bool ba(const l& l1, const l& l2, const l& l3) { return (l3.b-l1.b)*(l1.m-l2.m)<=(l2.b-l1.b)*(l1.m-l3.m); } void add(l li) { while(dq.size()>=2&&ba(dq[dq.size()-2], dq.back(), li)) dq.pop_back(); dq.push_back(li); } pair<long long, int> query(long long x) { while(dq.size()>=2&&ev(dq[0], x)>=ev(dq[1], x)) dq.pop_front(); return {ev(dq[0], x), dq[0].f}; } }; pair<long long, int> p(long long pen) { auto adj=[&](long long i) { if(i==1) return 0LL; return max(0LL, rr[i-1]-lr[i]+1)*max(0LL, rr[i-1]-lr[i]+1); }; vector<long long> g(n1+1, 0); vector<int> mf(n1+1, 0); g[0]=0; mf[0]=0; ch hull; hull.add({0, pen, 0}); for(long long i=1; i<=n1; i++) { long long ans=rr[i-1]; pair<long long, int> uj=hull.query(ans); g[i]=ans*ans+uj.first; mf[i]=mf[uj.second]+1; long long mt=-2LL*(lr[i]-1), nt=g[i]+(lr[i]-1)*(lr[i]-1)-adj(i)+pen; hull.add({mt, nt, i}); } return {g[n1], mf[n1]}; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { k1=k; long long jk=-1; if(n==0) return 0; vector<pair<long long, long long>> a(n); vector<long long> ul, tra; for(long long i=0; i<n; i++) { a[i]={min(r[i], c[i]),max(r[i], c[i])}; } sort(a.begin(), a.end(), [](const auto& a, const auto& b) { if(a.first!=b.first) return a.first<b.first; return a.second>b.second; }); for(auto &x: a) { if(x.second<=jk) continue; ul.push_back(x.first); tra.push_back(x.second); jk=x.second; } n1=ul.size(); lr.assign(n1+1, 0); rr.assign(n1+1, 0); for(long long i=1; i<=n1; i++) { lr[i]=ul[i-1]; rr[i]=tra[i-1]; } rr[0]=0; auto adj=[&](long long i) { if(i==1) return 0LL; return max(0LL, rr[i-1]-lr[i]+1)*max(0LL, rr[i-1]-lr[i]+1); }; long long l1=1, r2=1e9+7; while(l1<r2) { long long m=(l1+r2)/2; pair<long long, int> u=p(m); if(u.second>=k){l1=m+1;} else r2=m; } vector<long long> dp(n1+1,LLONG_MAX), cu(n1+1, LLONG_MAX); dp[0]=0; for(long long i=1; i<=k1; i++) { ch hull; hull.add({0, 0, 0}); for(int j=1; j<=n1; j++) { long long bt=hull.query(rr[j-1]).first; cu[j]=(rr[j-1])*(rr[j-1])+bt; if(dp[j]!=LLONG_MAX) { long long mt=-2LL*(lr[j]-1), nt=dp[j]+(lr[j]-1)*(lr[j]-1)-adj(j); hull.add({mt, nt, j}); } } swap(dp, cu); fill(cu.begin(), cu.end(), LLONG_MAX); } return dp[n1]; }

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...