Submission #427512

#TimeUsernameProblemLanguageResultExecution timeMemory
427512timmyfengAliens (IOI16_aliens)C++17
0 / 100
1 ms304 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000000; struct line { long long m, b, p; }; long long offset[N], edge[N]; long long floor_div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b != 0); } long long intersect(line a, line b) { return floor_div(a.b - b.b, b.m - a.m); } long long evaluate(line a, long long x) { return a.m * x + a.b; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { fill(edge, edge + m, -1); for (int i = 0; i < n; ++i) { if (r[i] > c[i]) { swap(r[i], c[i]); } edge[r[i]] = max(edge[r[i]], (long long) c[i]); } offset[0] = 1; for (int i = 1; i < m; ++i) { edge[i] = max(edge[i], edge[i - 1]); offset[i] = offset[i - 1] - 2 * i + 1; } long long ans = (long long) m * m; long long low = 0, high = ans; while (low < high) { long long mid = (low + high) / 2; long long cost = 0, photos = 0; deque<line> hull; int i = m - 1; for ( ; i >= 0 && edge[i] != -1; --i) { if (i == m - 1 || edge[i] != edge[i + 1]) { if (!hull.empty()) { cost = evaluate(hull[0], i) - offset[i]; photos = hull[0].p; } line add = {-2 * edge[i], 2 * edge[i] * edge[i] + cost + offset[min(i, (int) edge[i])], photos + 1}; while (hull.size() >= 2 && intersect(add, hull[hull.size() - 2]) >= intersect(add, hull.back())) { hull.pop_back(); } hull.push_back(add); } if (!hull.empty()) { while (hull.size() >= 2 && evaluate(hull[0], i - 1) > evaluate(hull[1], i - 1)) { hull.pop_front(); } } } cost = evaluate(hull[0], i) - (i == -1 ? 0 : offset[i]); photos = hull[0].p; if (photos <= k) { ans = cost - k * mid; high = mid; } else { low = mid + 1; } } 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...