제출 #249132

#제출 시각아이디문제언어결과실행 시간메모리
249132fedoseevtimofeyAliens (IOI16_aliens)C++14
4 / 100
2 ms384 KiB
#include <iostream> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <random> #include <iomanip> #include <functional> #include <cassert> using namespace std; typedef long long ll; typedef long double ld; #include "aliens.h" const ll Inf = 1e18; struct Line { ll k, b; Line(ll k, ll b) : k(k), b(b) {} ll f(ll x) { return x * k + b; } }; ld div_floor(ll a, ll b) { return (ld)a / b; } ld inter(Line a, Line b) { return div_floor(b.b - a.b, a.k - b.k); } struct CHT { vector <Line> lines; void add(Line a) { while (lines.size() >= 2) { Line b = lines.rbegin()[0]; Line c = lines.rbegin()[1]; if (inter(a, c) < inter(b, c)) lines.pop_back(); else break; } lines.push_back(a); } ll get(ll x) { int l = -1, r = (int)lines.size() - 1; while (r - l > 1) { int m = (l + r) >> 1; if (lines[m].f(x) >= lines[m + 1].f(x)) l = m; else r = m; } return lines[r].f(x); } }; ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) { vector <pair <int, int>> seg; for (int i = 0; i < n; ++i) { int cr = r[i], cc = c[i]; if (cc - cr < 0) { swap(cr, cc); } seg.push_back({cr, cc}); } sort(seg.begin(), seg.end(), [&] (pair <int, int> f, pair <int, int> s) { if (f.second != s.second) return f.second < s.second; else return f.first > s.first; }); { vector <pair <int, int>> nseg; int mn_l = m; for (int i = (int)seg.size() - 1; i >= 0; --i) { if (seg[i].first < mn_l) { nseg.push_back(seg[i]); mn_l = seg[i].first; } } seg = nseg; reverse(seg.begin(), seg.end()); } n = seg.size(); vector <ll> delta(n); for (auto &p : seg) ++p.second; for (int i = 1; i < n; ++i) { int inter = max(0, seg[i - 1].second - seg[i].first); delta[i] = -(ll)inter * inter; } for (int i = 0; i < n; ++i) { delta[i] += (ll)seg[i].first * seg[i].first; } auto get = [&] (ll pen) { vector <ll> dp(n + 1); dp[0] = 0; CHT c; c.add({-2 * seg[0].first, dp[0] + delta[0]}); for (int i = 1; i <= n; ++i) { dp[i] = pen + (ll)seg[i - 1].second * seg[i - 1].second + c.get(seg[i - 1].second); if (i < n) c.add({-2 * seg[i].first, dp[i] + delta[i]}); } int cnt = 0; int who = n; for (int i = n - 1; i >= 0; --i) { if (dp[who] == pen + (ll)seg[who - 1].second * seg[who - 1].second - 2LL * seg[who - 1].second * seg[i].first + dp[i] + delta[i]) { ++cnt; who = i; } } return make_pair(dp[n], cnt); }; ll L = 0, R = 1e18; while (R - L > 1) { ll M = (L + R) / 2; auto cur = get(M); if (cur.second > k) L = M; else R = M; } auto ans = get(R); return ans.first - ans.second * R; } #ifdef LOCAL int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif int n, m, k; cin >> n >> m >> k; vector<int> r(n), c(n); for (int i = 0; i < n; i++) { cin >> r[i] >> c[i]; } long long ans = take_photos(n, m, k, r, c); cout << ans << '\n'; } #endif
#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...