제출 #1010085

#제출 시각아이디문제언어결과실행 시간메모리
1010085phoenixAliens (IOI16_aliens)C++17
100 / 100
171 ms12792 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e18; struct CHT { struct line { ll a, b, i; ll f(ll x) { return a * x + b; }; }; ll intersect(line f1, line f2) { assert(f1.a != f2.a); return ceil(((double)f2.b - f1.b) / ((double)f1.a - f2.a)); } vector<line> st; vector<ll> p; void insert(line t) { if (st.empty()) { st.push_back(t); p.push_back(-INF); return; } while (!st.empty() && intersect(st.back(), t) <= p.back()) { p.pop_back(); st.pop_back(); } p.push_back(intersect(st.back(), t)); st.push_back(t); } int opt = 0; line query(ll x) { opt = min(opt, (int)st.size() - 1); while (opt + 1 < (int)st.size() && p[opt + 1] <= x) opt++; return st[opt]; } }; template<typename T1, typename T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) { return make_pair(a.first + b.first, a.second + b.second); }; int n; vector<long long> l; vector<long long> r; pair<long long, int> func(long long lambda) { vector<pair<ll, int>> dp(n + 1); vector<ll> t(n + 1); for (int i = 1; i <= n; i++) t[i] = max(0ll, r[i - 1] - l[i] + 1) * max(0ll, r[i - 1] - l[i] + 1); CHT convex; for (int i = 1; i <= n; i++) { convex.insert({(-2) * l[i], l[i] * l[i] + dp[i - 1].first - t[i], i - 1}); auto op = convex.query(r[i] + 1); dp[i] = {(r[i] + 1) * (r[i] + 1) + lambda + op.f(r[i] + 1), dp[op.i].second + 1}; } return dp[n]; } long long take_photos(int _n, int m, int k, vector<int> _r, vector<int> _c) { n = _n; for (int i = 0; i < n; i++) if (_r[i] > _c[i]) swap(_r[i], _c[i]); vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int a, int b) { if (_r[a] == _r[b]) return _c[a] > _c[b]; return _r[a] < _r[b]; }); l.push_back(-1); r.push_back(-1); for (int cur : ord) { if (r.empty() || r.back() < _c[cur]) { l.push_back(_r[cur]); r.push_back(_c[cur]); } } n = (int)l.size() - 1; k = min(k, n); long long lb = 0, rb = 1e13; while (rb - lb > 1) { long long mid = (lb + rb) / 2; if (func(mid).second <= k) rb = mid; else lb = mid; } return func(lb).first - k * lb; }
#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...