Submission #1193410

#TimeUsernameProblemLanguageResultExecution timeMemory
1193410simona1230Aliens (IOI16_aliens)C++20
4 / 100
43 ms328 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; struct line { long long a,b,id; line() {} line(long long _a,long long _b,int _id) { a=_a; b=_b; id=_id; } long long data(long long x) { return a*x+b; } }; deque<line> cht,cht2; int num; pair<int,int> p[200001]; bool cmp(pair<int,int> p1,pair<int,int> p2) { if(p1.second==p2.second)return p1.first<p2.first; return p1.second<p2.second; } long long sq(long long x) { return x*x; } double pt(line l1,line l2) { return (double)(l2.b-l1.b)/(double)(l1.a-l2.a); } void insert_(line l) { //cout<<l.a<<" - "<<l.b<<endl; while(cht.size()>=2&&pt(cht[cht.size()-1],l)<pt(cht[cht.size()-2],l))cht.pop_back(); cht.push_back(l); } int s,ch; long long dp[200001]; int cnt[200001]; long long value(long long x,int id) { s=min(s,(int)cht.size()-1); int h=s; long long ans=1e18; for(int i=s; i<cht.size(); i++) if(cht[i].id<id) { //cout<<cht[i].data(x)<<" "; if(ans>cht[i].data(x)) ch=cnt[cht[i].id]; ans=min(ans,cht[i].data(x)); if(ans==cht[i].data(x))h=i,ch=min(ch,cnt[cht[i].id]); else break; } else break; s=h; //cout<<endl; return ans; } void compute(long long c) { cht.clear(); dp[0]=sq(p[0].second-p[0].first+1)+c; cnt[0]=1; long long b=-2*p[1].first+dp[0]-sq(max(0,p[0].second-p[1].first+1))+sq(p[1].first); insert_({-2*p[1].first,b,0}); s=0; //cout<<"! "<<c<<" !!!"<<endl; for(int i=1; i<num; i++) { dp[i]=sq(p[i].second+1)+value(p[i].second,i)+c; //cout<<". "<<dp[i]<<endl; cnt[i]=ch+1; if(dp[i]>sq(p[i].second-p[0].first+1)+c) { dp[i]=sq(p[i].second-p[0].first+1)+c; //cout<<"? "<<dp[i]<<endl; cnt[i]=1; b=-2*p[i+1].first+dp[i]-sq(max(0,p[i].second-p[i+1].first+1))+sq(p[i+1].first); insert_({-2*p[i+1].first,b,i}); continue; } b=-2*p[i+1].first+dp[i]-sq(max(0,p[i].second-p[i+1].first+1))+sq(p[i+1].first); insert_({-2*p[i+1].first,b,i}); } //for(int i=0;i<num;i++) // cout<<dp[i]<<" "<<cnt[i]<<endl; } long long dp2[4001][4001]; 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++) p[i]= {min(r[i],c[i]),max(r[i],c[i])}; sort(p,p+n,cmp); for(int i=0; i<n; i++) { if(i!=0&&p[i].second==p[i-1].second)continue; while(num!=0&&p[num-1].first>=p[i].first)num--; p[num++]=p[i]; } long long ans=1e18; long long lf=0,rt=1e12; long long x=0; while(1) { //long long x=(lf+rt)/2; compute(x); if(cnt[num-1]<=k) { //cout<<"! "<<x<<" "<<cnt[num-1]<<endl; rt=x-1; ans=min(ans,dp[num-1]-cnt[num-1]*x); break; } x++; //else break; } /*long long ans2=1e18; for(int i=0;i<num;i++) { dp2[i][1]=sq(p[i].second-p[0].first+1); if(i==num-1)ans2=min(ans,dp2[i][1]); for(int j=2;j<=k;j++) { dp2[i][j]=1e18; for(int l=1;l<=i;l++) { //dp[i][j]=min(dp[i][j],dp[l-1][j-1]+sq(p[i].second-p[l].first+1)-sq(max(0,p[l-1].second-p[l].first+1))); dp2[i][j]=min(dp2[i][j],sq(p[i].second+1)+ (-2*p[l].first*p[i].second-2*p[l].first+dp2[l-1][j-1]-sq(max(0,p[l-1].second-p[l].first+1))+sq(p[l].first))); } if(i==num-1)ans2=min(ans2,dp2[i][j]); } } cout<<ans<<" "<<ans2<<endl; if(ans!=ans2)return -1;*/ return ans; }

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...