제출 #425244

#제출 시각아이디문제언어결과실행 시간메모리
425244vanicAliens (IOI16_aliens)C++14
12 / 100
145 ms7284 KiB
#include "aliens.h" #include <iostream> #include <cmath> #include <algorithm> #include <vector> using namespace std; typedef long long ll; const int maxn=4005; bool cmp(pair < int, int > a, pair < int, int > b){ return max(a.first, a.second)<max(b.first, b.second); } int n, m, k; ll dp[maxn][maxn]; pair < int, int > p[maxn]; ll pov[maxn][maxn]; void precompute(){ int maxx, maxy; int minx, miny; int raz; for(int i=0; i<n; i++){ maxx=0; maxy=0; minx=1e9; miny=1e9; for(int j=i; j<n; j++){ maxx=max(maxx, p[j].first); minx=min(minx, p[j].first); maxy=max(maxy, p[j].second); miny=min(miny, p[j].second); raz=abs(max(maxx, maxy)-min(minx, miny))+1; pov[i][j]=(ll)raz*raz; } } } ll take_photos(int nn, int mm, int kk, vector < int > r, vector < int > c){ n=nn; m=mm; k=kk; for(int i=0; i<n; i++){ if(r[i]<c[i]){ swap(r[i], c[i]); } p[i]={r[i], c[i]}; } sort(p, p+n); /* for(int i=0; i<n; i++){ cout << p[i].first << ' ' << p[i].second << endl; }*/ precompute(); /* for(int i=0; i<n; i++){ for(int j=i; j<n; j++){ cout << pov[i][j] << ' '; } cout << endl; }*/ for(int i=0; i<n; i++){ dp[i][1]=pov[0][i]; for(int j=2; j<=k; j++){ dp[i][j]=1e18; for(int l=0; l<i; l++){ dp[i][j]=min(dp[i][j], dp[l][j-1]+pov[l+1][i]); } } } ll sol=1e18; for(int i=1; i<=k; i++){ sol=min(sol, dp[n-1][i]); } return sol; }
#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...