Submission #1193325

#TimeUsernameProblemLanguageResultExecution timeMemory
1193325simona1230Aliens (IOI16_aliens)C++20
25 / 100
2096 ms596 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(cht2.size()>=2&&pt(cht2[cht2.size()-1],l)<pt(cht2[cht2.size()-2],l))cht2.pop_back(); cht2.push_back(l); } int s; long long value(long long x,int id) { long long ans=1e18; for(int i=s;i<cht.size();i++) if(cht[i].id<id) { //cout<<cht[i].data(x)<<" "; ans=min(ans,cht[i].data(x)); if(ans==cht[i].data(x))s=i; else break; } //cout<<endl; return ans; } long long dp[200001]; 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; /*for(int i=0;i<num;i++) { dp[i][1]=sq(p[i].second-p[0].first+1); if(i==num-1)ans=min(ans,dp[i][1]); for(int j=2;j<=k;j++) { dp[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))); dp[i][j]=min(dp[i][j],sq(p[i].second+1)+ (p[l].first*(-2)*p[i].second-2*p[l].first+dp[l-1][j-1]-sq(max(0,p[l-1].second-p[l].first+1))+sq(p[l].first))); } if(i==num-1)ans=min(ans,dp[i][j]); } }*/ for(int i=0;i<num;i++) { dp[i]=sq(p[i].second-p[0].first+1); long long 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}); } ans=dp[num-1]; cht=cht2; cht2.clear(); for(int j=2;j<=k;j++) { s=0; for(int i=0;i<num;i++) { dp[i]=sq(p[i].second+1)+value(p[i].second,i); long long b=-2*p[i+1].first+dp[i]-sq(max(0,p[i].second-p[i+1].first+1))+sq(p[i+1].first); if(i!=num-1)insert_({-2*p[i+1].first,b,i}); //cout<<dp[i]<<" "; } //cout<<endl; ans=min(ans,dp[num-1]); cht=cht2; cht2.clear(); } return ans; } /* long long value(long long x,int id) { if(cht.size()==1)return cht[0].data(x); long long ans=1e18; int l=0,r=cht.size()-2; while(l<=r) { int m=(l+r)/2; if(cht[m].id>=id) { r=m-1; } else { if(cht[m].data(x)<cht[m+1].data(x)) { ans=cht[m].data(x); r=m-1; } else { ans=cht[m+1].data(x); l=m+2; } } } 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...