Submission #440255

#TimeUsernameProblemLanguageResultExecution timeMemory
440255sebamarinAliens (IOI16_aliens)C++14
0 / 100
25 ms332 KiB
#include<bits/stdc++.h> using namespace std; // #define COMPILE 1 // #define DEBUG 1 typedef long long ll; typedef pair<ll,ll> ii; #define db(x) cout<<#x<<" = "<<x<<"\n"; #define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;i++) #define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define SZ(a) ((ll)(a).size()) #define ALL(a) a.begin(),a.end() #define mset(a,b) memset(a,b,sizeof(a)); #define pb push_back #define fst first #define snd second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // x,y -> -y,x ll sq(ll x){return x*x;} const ll N=4010,INF=1e18; ll n,m,k,h,to[N]; bool vis[N]; ii dp[N]; vector<ii>v; ii solve(ll i) { if(i==n)return {0ll,0ll}; if(vis[i])return dp[i]; vis[i]=1; ii res={INF,INF}; fore(k,i,n) { ii a=solve(k+1); ll b=sq(to[k]-v[i].fst+1); ll c=sq(max(0ll,to[k]-v[k+1].fst+1)); res=min(res,{a.fst+b+c+h,a.snd+1}); // cout<<i<<" "<<j<<" to "<<k+1<<" "<<j-1<<" with "<<cost<<" "<<a<<"+"<<b<<"-"<<c<<endl; } return dp[i]=res; } ii get_solve(ll alien) { h=alien; memset(vis,0,sizeof(vis)); return solve(0); } ll take_photos(int _n,int _m,int _k,vector<int>r,vector<int> c) { n=_n,m=_m,k=_k; map<ll,ll>mp; fore(i,0,n){ if(r[i]>c[i])swap(r[i],c[i]); v.pb({r[i],c[i]}); ll pr=mp[r[i]]; mp[r[i]]=max(pr,1ll*c[i]); } sort(ALL(v)); v.pb({INF,INF}); ll y=0; fore(i,0,n) { y=max(y,mp[v[i].fst]); to[i]=y; } #ifdef DEBUG cout<<"v: "<<endl;for(auto it:v)cout<<it.fst<<" "<<it.snd<<endl;cout<<"n: "<<n<<endl; cout<<"to: ";fore(i,0,n) cout<<to[i]<<" ";cout<<endl; #endif int ml=0,mr=m*m+10; while(ml<=mr) { h=(ml+mr)/2; memset(vis,0,sizeof(vis)); ii it=get_solve(h); if(it.snd<=k)mr=h-1; else ml=h+1; } ii res=get_solve(ml); // cout<<ml<<" : "<<res.fst<<" "<<res.snd<<endl; return res.fst-ml*res.snd; } #ifdef COMPILE int main() {FIN; cin>>n>>m>>k; vector<int>r(n),c(n); fore(i,0,n)cin>>r[i]>>c[i]; cout<<take_photos(n,m,k,r,c)<<"\n"; } #endif
#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...