Submission #1192354

#TimeUsernameProblemLanguageResultExecution timeMemory
1192354simona1230Aliens (IOI16_aliens)C++20
0 / 100
25 ms836 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[200001][128]; 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; if(num!=0&&p[num-1].first>=p[i].first)p[num-1]=p[i]; else 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; for(int i=0;i<num;i++) { dp[i][1]=sq(p[i].second-p[0].first+1); for(int j=2;j<=k;j++) { for(int l=1;l<=i;l++) { int rem=0; if(p[l].first<=p[l-1].second)rem=sq(p[l-1].second-p[l].first+1); dp[i][j]=min(dp[i][j],dp[l-1][j-1]+sq(p[i].second-p[l].first+1)-rem); } 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...