제출 #256620

#제출 시각아이디문제언어결과실행 시간메모리
256620tinjyuAliens (IOI16_aliens)C++14
0 / 100
34 ms640 KiB
#include "aliens.h" #include <iostream> #include <algorithm> using namespace std; struct node{ int x,y; }a[1000005]; long long int dp[50005][105],x[100005],y[100005]; bool cmp(node a,node b) { return a.x<b.x; } 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++) { a[i].x=r[i]; a[i].y=c[i]; if(a[i].y<a[i].x) { swap(a[i].x,a[i].y); } } sort(a,a+n,cmp); long long int cnt=1; x[1]=a[0].x; y[1]=a[0].y; for(int i=1;i<n;i++) { if(a[i].x>x[cnt] && a[i].y>y[cnt]) { cnt++; x[cnt]=a[i].x; y[cnt]=a[i].y; } else if(a[i].x==x[cnt] && a[i].y>y[cnt]) { x[cnt]=a[i].x; y[cnt]=a[i].y; } } n=cnt; for(int i=1;i<=n;i++) { //cout<<x[i]<<" "<<y[i]<<endl; } for(int i=0;i<=n;i++) { for(int j=0;j<=k;j++)dp[i][j]=99999999999999999; } dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { long long int nowy=y[i],nowx=x[i]; for(int l=i;l>=1;l--) { nowx=x[l]; dp[i][j]=min(dp[i][j],dp[l-1][j-1]+(nowy-nowx+1)*(nowy-nowx+1)); //cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<dp[l-1][j-1]<<" "<<nowx<<" "<<nowy<<endl; } } } long long int ans=10000000000000; for(int i=0;i<=k;i++) { ans=min(dp[n][i],ans); } 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...