제출 #69221

#제출 시각아이디문제언어결과실행 시간메모리
69221mr_bananaAliens (IOI16_aliens)C++17
25 / 100
2067 ms17796 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; const int MN=5000+10; long long inf=1e18; long long dp[MN][MN]; pair<int,int> p[MN]; long long sq(long long x){ return x*x; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for(int i=0;i<n;i++){ p[i]={min(r[i],c[i]),-max(r[i],c[i])-1}; } sort(p,p+n); int n1=unique(p,p+n)-p; n=0; int mx=-1; for(int i=0;i<n1;i++){ if(mx<-p[i].second){ p[n]={p[i].first,-p[i].second}; mx=p[n].second; n++; } } for(int i=0;i<n;i++){ for(int j=0;j<=k;j++){ dp[i+1][j]=inf; for(int l=0;l<=i;l++){ if(j){ dp[i+1][j]=min(dp[i+1][j],sq(p[i].second-p[l].first)+dp[l][j-1]); } } if(dp[i+1][j]!=inf && i+1<n){ dp[i+1][j]-=sq(max(0,p[i].second-p[i+1].first)); } } } return dp[n][k]; }
#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...