제출 #259995

#제출 시각아이디문제언어결과실행 시간메모리
259995ipaljakAliens (IOI16_aliens)C++14
60 / 100
110 ms8676 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " " << x << endl #define _ << " " << using llint = long long; const llint INF = 1e12; int n, m, k; vector<pair<int, int>> I, P; vector<llint> A, B; vector<int> hull; 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 ccw(int i, int j, int k) { return A[i] * (B[j] - B[k]) + A[j] * (B[k] - B[i]) + A[k] * (B[i] - B[j]); } void insert(int x, int *t) { while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), x) > 0) hull.pop_back(); hull.push_back(x); if (*t >= (int)hull.size()) *t = (int)hull.size() - 1; } pair<llint, int> dp(llint cost) { vector<llint> f(n, 0); vector<int> cnt(n, 0); hull.clear(); A.resize(n, 0); B.resize(n, 0); int t = 0; for (int i = 0; i < n; ++i) { llint c = (llint) I[i].second * I[i].second + cost; llint x = (llint) I[i].second; f[i] = INF; cnt[i] = -1; for (; t < (int) hull.size(); ++t) { llint a = A[hull[t]], b = B[hull[t]]; if (c + a * x + b > f[i]) { --t; break; } if (c + a * x + b == f[i]) { cnt[i] = min(cnt[i], cnt[hull[t]] + 1); } else { f[i] = c + a * x + b; cnt[i] = cnt[hull[t]] + 1; } } t = min((int) hull.size() - 1, t); t = max(0, t); llint single = (llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1) + cost; if (single < f[i]) { f[i] = single; cnt[i] = 1; } A[i] = -2LL * (I[i + 1].first - 1); B[i] = f[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); insert(i, &t); } return {f[n - 1], cnt[n - 1]}; } llint take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) { n = nn; m = mm; k = kk; 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); k = min(k, n); llint lo = 0, hi = (llint) 2 * m * m; while (lo < hi) { llint mid = (lo + hi) / 2; auto val = dp(mid); if (val.second > k) lo = mid + 1; else hi = mid; } auto sol = dp(lo); dp(lo - 1); return sol.first - (llint) k * lo; }
#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...