제출 #599519

#제출 시각아이디문제언어결과실행 시간메모리
599519jophyyjhAliens (IOI16_aliens)C++14
4 / 100
1 ms308 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). * Well, i really shouldn't have written "Too trivial" in [S1]. The following * observation is: if two segments (a1,b1) (a2,b2) satisfy a1 <= a2 and * b1 >= b2, the former's square completely contains the latter, so we shall * remove the latter. This means when we sort the points based on their b * values, a values are strictly increasing. * So in fact, [S3] = [S1] + [S2]! * * Time Complexity: O(n^2 * k) * Implementation 1.2 (only S1 fully solved) */ #include <bits/stdc++.h> #include "aliens.h" typedef long long ll; const int N_MAX = 500; const ll INF = 0x3f3f3f3f; inline ll sqr(int k) { return ll(k) * ll(k); } ll cover[N_MAX + 1][N_MAX + 1]; struct point_t { int i, j; }; inline bool operator==(const point_t& p1, const point_t& p2) { return p1.i == p2.i && p1.j == p2.j; } ll take_photos(int n, int m, int max_sqr, std::vector<int> row, std::vector<int> col) { if (max_sqr != n) return -1; // bye std::vector<point_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 point_t& p1, const point_t& p2) { return p1.j < p2.j || (p1.j == p2.j && p1.i > p2.i); }); std::vector<bool> skipped(n, false); for (int k = n - 1, suffix_min = INF; k >= 0; k--) { if (values[k].i >= suffix_min) skipped[k] = true; suffix_min = std::min(suffix_min, values[k].i); } ll area = 0; for (int k = 0, prev = -1; k < n; k++) { if (skipped[k]) continue; area += sqr(values[k].j - values[k].i + 1) - sqr(std::max(prev - values[k].i + 1, 0)); prev = values[k].j; } return area; }
#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...