Submission #786510

#TimeUsernameProblemLanguageResultExecution timeMemory
786510LuoBoAliens (IOI16_aliens)C++14
0 / 100
1 ms2260 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; const int MAXN=100010; struct node { int x, y; } a[MAXN]; long long f[510][510]; long long min(long long x,long long y) { return x<y ? x : y ; } 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++) { if ( r[i]>c[i] ) { a[i+1].x=c[i]+1; a[i+1].y=r[i]+1; } else { a[i+1].x=r[i]+1; a[i+1].y=c[i]+1; } } int ans=1e9; memset(f,127,sizeof(f)); f[0][0]=0; for (int i=1;i<=n;i++) { for (int j=0;j<i;j++) { for (int opt=1;opt<=k;opt++) { f[i][opt]=min(f[i][opt],f[j][opt-1]+(a[i].x-a[j+1].x+1)*(a[i].x-a[j+1].x+1)); } } } for (int opt=1;opt<=k;opt++) ans=min(ans,f[n][opt]); return ans; }
#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...