제출 #261671

#제출 시각아이디문제언어결과실행 시간메모리
261671mjkocijanAliens (IOI16_aliens)C++14
0 / 100
4 ms4224 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back typedef long long ll; typedef long double ld; typedef pair<ll, ll> ii; typedef pair<ld, ld> dd; typedef pair<ii, ll> pi; #define MAXN 1001001 ll N, M, K, vn; int mx[MAXN], cnt[MAXN]; ll dp[MAXN]; vector<ii> v; vector<pi> hal; ll ccw(ii A, ii B, ii C) { return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y); } ll solve(ll x) { hal.clear(); for (int i = 0; i < vn; i++) { ll ix = -2 * (v[i].X - 1); ll iy = dp[i] + (v[i].X - 1) * (v[i].X - 1) - (i ? max(0LL, v[i - 1].Y + 1 - v[i].X) : 0); while (hal.size() > 1 && ccw(hal[hal.size() - 2].X, hal.back().X, {ix, iy}) >= 0) hal.pop_back(); hal.pb({{ix, iy}, i}); int lo = 0, hi = hal.size() - 1; while (lo < hi) { int mid = (lo + hi) / 2; if (hal[mid].X.X * v[i].Y + hal[mid].X.Y > hal[mid + 1].X.X * v[i].Y + hal[mid + 1].X.Y) lo = mid + 1; else hi = mid; } dp[i + 1] = hal[lo].X.X * v[i].Y + hal[lo].X.Y + x + v[i].Y * v[i].Y; cnt[i + 1] = 1 + cnt[hal[lo].Y]; } return cnt[vn]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { memset(mx, -1, sizeof mx); N = n; M = m; K = k; for (int i = 0; i < n; i++) { if (r[i] > c[i]) { swap(r[i], c[i]); } } for (int i = 0; i < n; i++) { mx[r[i]] = max(mx[r[i]], c[i]); } int cu = -1; for (int i = 0; i <= m; i++) { if (mx[i] > cu) { cu = mx[i]; v.pb({i, cu}); } } vn = v.size(); ll lo = 0, hi = M * M; while (lo < hi) { ll mid = (lo + hi) / 2; if (solve(mid) > K) lo = mid + 1; else hi = mid; } return dp[vn] - lo * vn; }
#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...