제출 #599020

#제출 시각아이디문제언어결과실행 시간메모리
599020jophyyjhAliens (IOI16_aliens)C++14
0 / 100
1 ms312 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 */ #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); } struct seg_t { int i, j; }; 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) { std::vector<seg_t> values(n); for (int k = 0; k < n; k++) values[k].i = std::min(row[k], col[k]), values[k].j = std::max(row[k], col[k]); std::sort(values.begin(), values.end(), [](const seg_t& s1, const seg_t& s2) { return s1.j < s2.j || (s1.j == s2.j && s1.i < s2.i); }); values.insert(values.begin(), seg_t{-1, -1}); cover[0][0] = 0; for (int squares = 1; squares <= max_sqr; squares++) cover[0][squares] = INF; int last_idx = -1; for (int k = 1, prev_j = -1; k <= n; k++) { if (prev_j == values[k].j) continue; prev_j = values[k].j, last_idx = k; cover[k][0] = INF; for (int squares = 1; squares <= max_sqr; squares++) { cover[k][squares] = INF; for (int m = k - 1, left = 0x3f3f3f; m >= 0; m--) { left = std::min(left, values[m + 1].i); cover[k][squares] = std::min( cover[k][squares], cover[m][squares - 1] + sqr(values[k].j - left + 1) - sqr(std::max(values[m].j - left + 1, 0)) ); } } } ll ans = INF; for (int squares = 1; squares <= max_sqr; squares++) ans = std::min(ans, cover[last_idx][squares]); 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...