제출 #1057430

#제출 시각아이디문제언어결과실행 시간메모리
1057430TAhmed33Aliens (IOI16_aliens)C++98
60 / 100
1078 ms1048576 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; //#include "grader.cpp" const ll inf = 1e16; typedef long double ld; const ld eps = 1e-9; inline ll sq (ll x) { return x * x; } struct CHT { deque <pair <ll, ll>> dd; void init () { } ld inter (pair <ll, ll> x, pair <ll, ll> y) { return 1.0 * (x.second - y.second) / (y.first - x.first); } ll query (ll x) { while (dd.size() >= 2) { if (inter(dd[dd.size() - 1], dd[dd.size() - 2]) <= x) { break; } dd.pop_back(); } return dd.back().first * x + dd.back().second; } void insert (ll x, ll y) { pair <ll, ll> g = {x, y}; while (dd.size() >= 2 && inter(g, dd[0]) > inter(dd[0], dd[1]) + eps) { dd.pop_front(); } dd.push_front(g); } }; ll take_photos (int n, int m, int k, vector <int> r, vector <int> c) { array <ll, 2> a[n + 2]; for (int i = 0; i < n; i++) { if (r[i] < c[i]) { swap(r[i], c[i]); } c[i]++; r[i]++; a[i + 1] = {c[i], r[i]}; } sort(a + 1, a + n + 1, [&] (array <ll, 2> &x, array <ll, 2> &y) { return x[0] == y[0] ? x[1] > y[1] : x[0] < y[0]; }); ll mx = 0; array <ll, 2> b[n + 2]; int d = 0; for (int i = 1; i <= n; i++) { if (mx >= a[i][1]) { continue; } b[++d] = a[i]; mx = a[i][1]; } n = d; ll dp[n + 2][k + 2] = {}; for (int i = 1; i <= n; i++) { a[i] = b[i]; } a[n + 1] = {m + 1, m + 1}; for (int i = 1; i <= n; i++) { dp[i][0] = inf; } for (int j = 1; j <= k; j++) { CHT cur; cur.init(); for (int i = n; i >= 1; i--) { cur.insert(-2 * a[i][1], sq(a[i][1]) + 2 * a[i][1] - sq(max(0ll, a[i][1] - a[i + 1][0] + 1)) + dp[i + 1][j - 1]); dp[i][j] = cur.query(a[i][0]) + sq(a[i][0]) - 2 * a[i][0] + 1; } } return dp[1][k]; }
#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...