제출 #657848

#제출 시각아이디문제언어결과실행 시간메모리
657848benjaminkleynAliens (IOI16_aliens)C++17
100 / 100
799 ms15752 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Line { mutable ll k, m, p, cnt; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { static const ll inf = LLONG_MAX; ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m, ll cnt) { auto z = insert({k, m, 0, cnt}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } pair<ll,ll> query(ll x) { assert(!empty()); auto l = lower_bound(x); return {l->k * x + l->m, l->cnt}; } } cht; #define COL first #define ROW second vector<pair<ll,ll>> pts, dp; pair<ll,ll> calc(int n, ll cost) { dp[0] = {0, 0}; cht.clear(); for (int i = 1; i <= n; i++) { ll gradient = - 2 * (pts[i].ROW - 1); ll square = (pts[i].ROW - 1); ll overlap = max(pts[i - 1].COL - pts[i].ROW + 1, 0LL); cht.add(-gradient, -(dp[i - 1].first + square * square - overlap * overlap + cost), dp[i - 1].second); pair<ll,ll> res = cht.query(pts[i].COL); dp[i] = {-res.first + pts[i].COL * pts[i].COL, res.second + 1}; } return dp[n]; } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector<pair<ll,ll>> temp_pts(n); for (int i = 0; i < n; i++) { if (r[i] > c[i]) swap(r[i], c[i]); temp_pts[i] = {c[i], r[i]}; } sort(temp_pts.begin(), temp_pts.end()); pts.push_back({-1, -1}); for (pair<ll,ll> pt : temp_pts) { while (pts.size() && pts.back().ROW >= pt.ROW) pts.pop_back(); pts.push_back(pt); } n = pts.size() - 1; dp.resize(n + 1); ll lo = 0, hi = 1e12, res = 1e12, mid; while (lo <= hi) { mid = (lo + hi) / 2; calc(n, mid); if (dp[n].second <= k) hi = mid - 1, res = mid; else lo = mid + 1; } calc(n, res); return dp[n].first - k * res; }
#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...