Submission #1192712

#TimeUsernameProblemLanguageResultExecution timeMemory
1192712simona1230Aliens (IOI16_aliens)C++20
4 / 100
0 ms840 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; 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(int x) { return x*x; } long long dp[5001][4001]; long long f[5001][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]; } /*cout<<num<<endl; for(int i=0;i<num;i++) cout<<p[i].first<<" "<<p[i].second<<endl;*/ for(int i=0;i<num;i++) { for(int j=0;j<=k;j++) { dp[i][j]=1e18; } } long long ans=1e18; dp[0][1]=sq(p[0].second-p[0].first+1); f[0][1]=p[0].first; for(int i=1;i<num;i++) { dp[i][1]=sq(p[i].second-p[0].first+1); for(int j=1;j<=k;j++) { long long h1=dp[i-1][j-1]+sq(p[i].second-p[i].first+1); if(p[i].first<=p[i-1].second)h1-=sq(p[i-1].second-p[i].first+1); long long h2=dp[i-1][j]+sq(p[i].second-f[i-1][j]+1)-sq(p[i-1].second-f[i-1][j]+1); if(h1<h2)dp[i][j]=h1,f[i][j]=p[i].first; else dp[i][j]=h2,f[i][j]=f[i-1][j]; //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; if(i==num-1)ans=min(ans,dp[i][j]); } } ans=min(ans,dp[num-1][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...