제출 #435853

#제출 시각아이디문제언어결과실행 시간메모리
435853HegdahlAliens (IOI16_aliens)C++17
4 / 100
10 ms204 KiB
#include <bits/stdc++.h> #include "aliens.h" #define ar array using namespace std; using ll = long long; int n, m, k; vector<ar<ll, 2>> a; const ll INF = 1LL<<60; ll sq(ll a) { return a*a; } pair<ll, int> solve(ll penalty) { vector<ll> cost(n+1, INF); vector<int> used(n+1, 0); cost[0] = 0; for (int i = 0; i < n; ++i) { int pr = i==0 ? -1 : a[i-1][1]; int l = a[i][0], r = a[i][1]; for (int j = i+1; j <= n; ++j) { r = a[j-1][1]; ll c = cost[i] + sq(r-l+1) - sq(max(0, pr-l+1)) + penalty; if (c < cost[j]) { cost[j] = c; used[j] = used[i]+1; } } } return {cost[n], used[n]}; } ll take_photos(int n_, int m_, int k_, vector<int> r_, vector<int> c_) { n = n_, m = m_, k = k_; a.resize(n); for (int i = 0; i < n; ++i) a[i] = {min(r_[i], c_[i]), max(r_[i], c_[i])}; sort(a.begin(), a.end(), [&](auto p0, auto p1) { if (p0[0] != p1[0]) return p0[0] < p1[0]; return p0[1] > p1[1]; }); { decltype(a) na; int mxr = -1e9; for (int i = 0; i < n; ++i) { if (a[i][1] > mxr) { mxr = a[i][1]; na.push_back(a[i]); } } a = move(na); n = (int)a.size(); } ll ans = INF; ll lo = -INF, hi = INF; while (lo != hi) { ll ce = lo + (hi-lo)/2; auto [cost, used] = solve(ce); if (used > k) lo = ce+1; else { hi = ce; ans = min(ans, cost - used*ce); } } return ans; }
#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...