Submission #1193399

#TimeUsernameProblemLanguageResultExecution timeMemory
1193399simona1230Aliens (IOI16_aliens)C++20
4 / 100
1 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; 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)<<" "; ans=min(ans,cht[i].data(x)); if(ans==cht[i].data(x))h=i; else break; } else break; s=h; //cout<<endl; return ans; } long long dp[200001]; int cnt[200001]; 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]=cnt[s]+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 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) { rt=x-1; ans=min(ans,dp[num-1]-cnt[num-1]*x); break; } x++; //else break; } 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...