제출 #599040

#제출 시각아이디문제언어결과실행 시간메모리
599040jophyyjhAliens (IOI16_aliens)C++14
0 / 100
50 ms2260 KiB
/** * I don't feel like fully solving this, so maybe i'll just score some partials. * * [S1] Too trivial * [S2] Each point lies on the main diagonal. Clearly, no two squares should have * common squares, which means the points are partitioned into contiguous * segments. O(n^2 * k) dp kills it. * [S3] Maybe we can somehow sort the points based on their columns, then apply [S2]? * Yep, pretty much analagous to [S2]. The key here is that if (2,5), (3,5), * the square that covers (2,5) must cover (3,5). * * Time Complexity: O(n^2 * k) * Implementation 1 ([S3] hold, only solves the first two) */ #include <bits/stdc++.h> #include "aliens.h" typedef long long ll; const int N_MAX = 500; const ll INF = 0x3f3f3f3f3f3f; inline ll sqr(int k) { return ll(k) * ll(k); } ll cover[N_MAX + 1][N_MAX + 1]; ll take_photos(int n, int m, int max_sqr, std::vector<int> row, std::vector<int> col) { if (max_sqr == n) return max_sqr; std::sort(row.begin(), row.end()); cover[0][0] = 0; for (int s = 1; s <= max_sqr; s++) cover[0][s] = INF; for (int k = 0; k < n; k++) { cover[k + 1][0] = INF; for (int s = 1; s <= max_sqr; s++) { cover[k + 1][s] = INF; for (int m = 0; m <= k; m++) { // [m,k] cover[k + 1][s] = std::min( cover[k + 1][s], cover[m][s - 1] + sqr(row[k] - row[m] + 1) ); } } } ll ans = INF; for (int s = 1; s <= max_sqr; s++) ans = std::min(ans, cover[n][s]); 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...