제출 #672372

#제출 시각아이디문제언어결과실행 시간메모리
672372Eae02Aliens (IOI16_aliens)C++17
4 / 100
2 ms340 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x),end(x) struct Line { mutable ll k, m, p; ll howManyPhotos; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return false; } 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 howManyPhotos) { auto z = insert({k, m, 0, howManyPhotos}), 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 make_pair(l.k * x + l.m, l.howManyPhotos); } }; ll take_photos(int n, int m, int K, vector<int> r, vector<int> c) { vector<pair<ll, ll>> intvs; for (int i = 0; i < n; i++) { intvs.emplace_back(min(r[i], c[i]), -max(r[i], c[i])); } sort(all(intvs)); vector<pair<ll, ll>> st; for (auto [l, r] : intvs) { if (st.empty() || -r > st.back().second) st.emplace_back(l, -r); } //for (auto [l, r] : st) { // cerr << "intv " << l << " " << r << "\n"; //} constexpr ll inf = LLONG_MAX; auto square = [&] (ll x) { return x * x; }; auto alienTrick = [&] (ll cost) -> pair<ll, ll> { // (ans, howManyPhotos) vector<pair<ll, ll>> dp(st.size() + 1); dp[st.size()] = {0,0}; LineContainer lc; auto addToLC = [&] (ll ie) { if (ie == 0) return; ll ex = st[ie-1].second + 1; ll bx = st[ie].first; ll k = -2 * ex; ll m = dp[ie].first + square(ex) - square(max(ex - bx, 0LL)); lc.add(-k, -m, dp[ie].second); }; for (ll i = (ll)st.size() - 1; i >= 0; i--) { pair<ll, ll> ans = { dp[st.size()].first + square(st.back().second - st[i].first + 1) + cost, 1LL }; /*for (ll ie = i + 1; ie < (ll)st.size(); ie++) { ll ex = st[ie-1].second + 1; ll bx = st[ie].first; ans = min(ans, dp[ie][remk - 1] + square(ex) - 2 * ex * st[i].first + square(st[i].first) - square(max(ex - bx, 0LL)) ); }*/ if (!lc.empty()) { auto lcq = lc.query(st[i].first); ans = min(ans, make_pair(-lcq.first + square(st[i].first) + cost, lcq.second + 1)); } dp[i] = ans; addToLC(i); } return dp[0]; }; ll lo = 0; ll hi = 1E9; while (hi > lo) { ll mid = (lo + hi) / 2; auto [ans, howManyPhotos] = alienTrick(mid); if (howManyPhotos > K) lo = mid + 1; else hi = mid; } return alienTrick(lo).first - lo * K; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:54:15: warning: unused variable 'inf' [-Wunused-variable]
   54 |  constexpr ll inf = LLONG_MAX;
      |               ^~~
#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...