제출 #529133

#제출 시각아이디문제언어결과실행 시간메모리
529133msg555Aliens (IOI16_aliens)C++14
25 / 100
2069 ms448 KiB
#include "aliens.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; long long squared(int x) { return 1ll * x * x; } long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) { vector<pair<int, int> > A; for (int i = 0; i < N; i++) { int ri = R[i]; int ci = C[i]; if (ri > ci) swap(ri, ci); A.push_back(make_pair(ci, ci - ri)); } sort(A.begin(), A.end()); int j = 0; for (auto p : A) { while (j > 0 && p.second >= A[j - 1].second + p.first - A[j - 1].first) { --j; } A[j++] = p; } A.resize(j); N = j; long long INF = squared(M + 1); vector<long long> DP(N + 1, INF); DP[0] = 0; for (int k = 0; k < K; k++) { for (int i = 1; i < N; i++) { DP[i] -= squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first)); } for (int i = N; i > 0; i--) { DP[i] = INF; for (int j = 0; j < i; j++) { DP[i] = min( DP[i], DP[j] + squared(1 + A[j].second + A[i - 1].first - A[j].first) ); } } } return DP[N]; }
#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...