제출 #119977

#제출 시각아이디문제언어결과실행 시간메모리
119977LawlietAliens (IOI16_aliens)C++14
12 / 100
231 ms200164 KiB
#include <bits/stdc++.h> #include "aliens.h" #define X first #define Y second #define MAXK 510 #define MAXN 50010 #define INF 1000000000000000000LL using namespace std; typedef long long int lli; typedef pair<lli,lli> pii; lli N, M, K; lli dp[MAXN][MAXK]; vector<pii> points; lli cost(int i, int j) { lli dif = points[i].X - points[j].X + 1; return dif*dif; } lli DP(int i, int k) { if(dp[i][k] != -1) return dp[i][k]; if(i == 0) return dp[i][k] = 0; if(k == 0) return dp[i][k] = INF; dp[i][k] = INF; for(int g = 1 ; g <= i ; g++) dp[i][k] = min(dp[i][k] , DP(g - 1 , k - 1) + cost(i , g)); return dp[i][k]; } long long int take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { N = n; M = m; K = k; memset(dp , -1 , sizeof(dp)); points.push_back({-1 , -1}); for(int g = 0 ; g < n ; g++) points.push_back({c[g] , r[g]}); sort(points.begin(),points.end()); return DP(n , k); } /*int main() { int nn, mm, kk; int n1, n2; scanf("%d %d %d",&nn,&mm,&kk); vector<int> xx, yy; for(int g = 0 ; g < nn ; g++) { scanf("%d %d",&n1,&n2); xx.push_back(n1); yy.push_back(n2); } printf("%lld\n",take_photos(nn , mm , kk , xx , yy)); }*/
#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...