Submission #259486

#TimeUsernameProblemLanguageResultExecution timeMemory
259486ipaljakAliens (IOI16_aliens)C++14
0 / 100
1 ms384 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " " << x << endl #define _ << " " << using llint = long long; const int MAXN = 5e4 + 5; const llint INF = 1e17; vector<pair<int, int>> I, P; struct Event { int x, type, id; Event() {} Event(int x, int type, int id) : x(x), type(type), id(id) {} friend bool operator<(const Event &A, const Event &B) { if (A.x == B.x) return A.type < B.type; return A.x < B.x; } }; vector<pair<int, int>> get_intervals(int n, const vector<int> &r, const vector<int> &c) { vector<Event> e; for (int i = 0; i < n; ++i) { int lo = min(r[i], c[i]); int hi = max(r[i], c[i]); e.emplace_back(lo, 0, i); e.emplace_back(hi, 1, i); } sort(e.begin(), e.end()); multiset<int> ms; vector<pair<int, int>> ret; for (const auto &p : e) { if (p.type == 0) { ms.insert(p.x); continue; } int lo = min(r[p.id], c[p.id]); ms.erase(ms.find(lo)); if (ms.empty() || *ms.begin() > lo) ret.emplace_back(lo, p.x); } return ret; } llint take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]); I = get_intervals(n, r, c); n = (int)I.size(); vector<llint> dp_prev(n, 0), dp_curr(n, 0); stack<pair<llint, llint>> env_prev, env_curr; for (int i = 0; i < n; ++i) { dp_prev[i] = (llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1); if (i == n - 1) { env_prev.push({0, 0}); continue; } llint A = -2LL * (I[i + 1].first - 1); llint B = dp_prev[i] + (llint)(I[i + 1].first - 1) * (I[i + 1].first - 1) - (llint)max(0, I[i].second - I[i + 1].first + 1) * max(0, I[i].second - I[i + 1].first + 1); env_prev.push({A, B}); } for (int i = 1; i < k; ++i) { int t = 0; for (int j = 0; j < n; ++j) { llint c = (llint) I[j].second * I[j].second; llint x = (llint) I[j].second; llint env_a = env_prev.top().first, env_b = env_prev.top().second; dp_curr[j] = c + env_a * x + env_b; env_prev.pop(); while (!env_prev.empty() && t <= j) { auto p = env_prev.top(); if (c + p.first * x + p.second <= dp_curr[j]) { dp_curr[j] = c + p.first * x + p.second; env_a = p.first; env_b = p.second; env_prev.pop(); ++t; continue; } break; } env_prev.push({env_a, env_b}); if (j == n - 1) { env_curr.push({0, 0}); continue; } llint A = -2LL * (I[j + 1].first - 1); llint B = dp_prev[t] + (llint)(I[j + 1].first - 1) * (I[j + 1].first - 1) - (llint)max(0, I[j].second - I[j + 1].first + 1) * max(0, I[j].second - I[j + 1].first + 1); env_curr.push({A, B}); } swap(dp_prev, dp_curr); while (!env_prev.empty()) env_prev.pop(); swap(env_prev, env_curr); } return dp_prev[n - 1]; }
#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...