제출 #1046861

#제출 시각아이디문제언어결과실행 시간메모리
1046861Gromp15Aliens (IOI16_aliens)C++17
100 / 100
100 ms8872 KiB
#include "aliens.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> #define ar array #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define ll long long using namespace std; template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } const ll INF = 1e18; const int nax = 1e5 + 5; ar<ll, 4> d[nax]; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<ar<int, 2>> a(n); for (int i = 0; i < n; i++) { a[i] = {r[i], c[i]}; if (r[i] > c[i]) swap(a[i][0], a[i][1]); } sort(all(a)); int mx = -1; vector<ar<int, 2>> b; for (int i = 0; i < n; i++) { int r = i; while (r+1 < n && a[r+1][0] == a[r][0]) r++; if (a[r][1] > mx) { b.push_back({a[r][0], a[r][1]}); mx = a[r][1]; } i = r; } swap(a, b); n = sz(a); ll L = 0, R = 1e12, ans = -1; while (L <= R) { ll mid = (L+R)/2; vector<ar<ll, 3>> dp(n+1, {INF, INF, -INF}); dp[0] = {0, 0, 0}; auto sq = [&](int x) { return (ll)x * x; }; auto f = [&](int j) { return dp[j][0] + sq(a[j][0]) - 2 * a[j][0] - (j ? sq(max(0, a[j-1][1] - a[j][0] + 1)) : 0); }; int dl = -1, dr = 0; d[++dl] = {-2 * a[0][0], f(0), 0, 0}; auto query = [&](int p, int pos) { return d[p][0] * pos + d[p][1]; }; auto inter = [&](const ar<ll, 4>& x1, const ar<ll, 4>& x2) { return (double)(x2[1] - x1[1]) / (x1[0] - x2[0]); }; for (int i = 1; i <= n; i++) { ll C = sq(a[i-1][1]) + 2 * a[i-1][1] + 1 + mid; int cur = a[i-1][1]; while (dl+1 <= dr && query(dl+1, cur) < query(dl, cur)) dl++; dp[i][0] = query(dl, cur) + C; for (int j = dl; j <= dr; j++) { if (query(j, cur) == query(dl, cur)) { ckmin(dp[i][1], d[j][2] + 1); ckmin(dp[i][2], d[j][3] + 1); } else break; } if (i < n) { ar<ll, 4> nw{-2 * a[i][0], f(i), dp[i][1], dp[i][2]}; while (dr-dl >= 1 && inter(d[dr-1], nw) <= inter(d[dr-1], d[dr])) dr--; d[++dr] = nw; } } if (dp[n][1] <= k) { int u = min(k, int(dp[n][2])); ans = dp[n][0] - u * mid; R = mid-1; } else L = mid+1; } 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...