제출 #259897

#제출 시각아이디문제언어결과실행 시간메모리
259897ipaljakAliens (IOI16_aliens)C++14
60 / 100
2001 ms8824 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; } // y = ax + b = cx + d // x(a - c) == d - b double intersect(pair<llint, llint> &A, pair<llint, llint> &B) { return (double) (B.second - A.second) / (A.first - B.first); } void replace(stack<pair<llint, llint>> &src, stack<pair<llint, llint>> &dest) { while (!src.empty()) { if (dest.size() < 3) { dest.push(src.top()); src.pop(); continue; } pair<llint, llint> A, B, C; while (dest.size() >= 3) { B = dest.top(); dest.pop(); A = dest.top(); C = src.top(); if (intersect(A, C) < intersect(B, C)) continue; dest.push(B); break; } dest.push(C); src.pop(); } } 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(); I.emplace_back(1e9, 1e9); 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); 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_curr.push({A, B}); } replace(env_curr, env_prev); 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 = -INF, env_b = -INF; dp_curr[j] = INF; 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; } if (env_a != -INF || env_b != -INF) { env_prev.push({env_a, env_b}); --t; } dp_curr[j] = min(dp_curr[j], dp_prev[j]); llint A = -2LL * (I[j + 1].first - 1); llint B = dp_curr[j] + (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(); replace(env_curr, env_prev); } 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...