# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
21163 | 2017-04-06T20:43:04 Z | sbansalcs | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KB |
#include "aliens.h" #include <iostream> using namespace std; typedef long long ll; const int N = 4005; const int M = 1e6+2; const ll inf=1e12; int arr[M]; int vis[M]; // int cost[N][N]; vector<int> vt; int n2; ll dp[2][N]; long long take_photos(int n, int m, int k, std::vector<int> vt1, std::vector<int> vt2) { for(int i=0;i<n;i++) { if(vt2[i]>vt1[i]) { swap(vt2[i],vt1[i]); } if(vis[vt1[i]]) arr[vt1[i]]=min(arr[vt1[i]],vt2[i]); else { arr[vt1[i]]=vt2[i]; vis[vt1[i]]=1; vt.push_back(vt1[i]); } } sort(vt.begin(),vt.end()); int n2=vt.size(); // for(int i=0;i<n2;i++) { // cout<<i<<" : "<<vt[i]<<" , "<<arr[vt[i]]<<endl; // } // for(int i=0;i<n2;i++) { // int s=1e7; // for(int j=i;j<n2;j++) { // s=min(arr[vt[j]],s); // cost[i][j]=1+vt[j]-s;cost[i][j]*=cost[i][j]; // cout<<i<<" "<<j<<" : "<<cost[i][j]<<endl; // } // } // for(int i=0;i<n2;i++) { // for(int j=1;j<=i+1 && j<=k;j++) { // if(j==1) // } // } int a,b,s;ll f; for(int i=0;i<=k;i++) { a=i&1;b=a^1; for(int j=0;j<n2;j++) { dp[a][j]=inf; s=1e7; if(i!=0 && i<=j+1) { for(int l=j;l>=0;l--) { s=min(s,arr[vt[l]]); f=vt[j]+1-s;f*=f; if(l==0) { dp[a][j]=min(dp[a][j],f); } else { dp[a][j]=min(dp[a][j],dp[b][l-1]+f); } } } // cout<<i<<" "<<j<<" : "<<dp[a][j]<<endl; } } return dp[k&1][n2-1]; }