제출 #432955

#제출 시각아이디문제언어결과실행 시간메모리
432955yuto1115Aliens (IOI16_aliens)C++17
25 / 100
2083 ms14476 KiB
#include "aliens.h" #include <bits/stdc++.h> #define rep(i, n) for(ll i = 0; i < ll(n); i++) #define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++) #define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back using namespace std; using ll = long long; using P = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vp = vector<P>; using vvp = vector<vp>; using vb = vector<bool>; using vvb = vector<vb>; using vs = vector<string>; template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } const int inf = 1001001001; const ll linf = 1001001001001001001; // Convex Hull Trix (Minimum) class li_chao_tree { int n; vl xs; // y = ax + b vl a, b; vi ls, rs; ll eval(ll na, ll nb, int x) { return na * xs[x] + nb; } void add(int k, ll na, ll nb) { int l = ls[k], r = rs[k], m = (l + r) / 2; if (l + 1 == r) { if (eval(a[k], b[k], l) > eval(na, nb, l)) { a[k] = na; b[k] = nb; } return; } if (eval(a[k], b[k], l) <= eval(na, nb, l) and eval(a[k], b[k], r) <= eval(na, nb, r)) return; if (eval(a[k], b[k], l) >= eval(na, nb, l) and eval(a[k], b[k], r) >= eval(na, nb, r)) { a[k] = na; b[k] = nb; return; } if (eval(a[k], b[k], m) > eval(na, nb, m)) { swap(a[k], na); swap(b[k], nb); } if (eval(a[k], b[k], l) > eval(na, nb, l)) { add(2 * k, na, nb); return; } if (eval(a[k], b[k], r) > eval(na, nb, r)) { add(2 * k + 1, na, nb); return; } } void init(const vl &_xs) { n = 1; while (n < (int) _xs.size()) n *= 2; a.assign(2 * n, 0); b.assign(2 * n, linf); ls.resize(2 * n); rs.resize(2 * n); rep(i, n) { ls[n + i] = i; rs[n + i] = i + 1; } rrep(i, n) { ls[i] = ls[2 * i]; rs[i] = rs[2 * i + 1]; } xs.resize(n + 1, _xs.back() + 1); rep(i, _xs.size()) xs[i] = _xs[i]; } public: li_chao_tree(const vl &_xs) { assert(is_sorted(all(xs))); init(_xs); } li_chao_tree(int n) { vl v(n); iota(all(v), 0); init(v); } ll get_min(int i) { assert(0 <= i and i < n); int x = i; i += n; ll res = linf; while (i >= 1) { chmin(res, eval(a[i], b[i], x)); i >>= 1; } return res; } void add_line(ll na, ll nb) { add(1, na, nb); } void add_segment(int l, int r, ll na, ll nb) { assert(0 <= l and l <= r and r <= n); l += n, r += n; while (l < r) { if (l & 1) add(l++, na, nb); if (r & 1) add(--r, na, nb); l >>= 1, r >>= 1; } } }; ll take_photos(int n, int m, int k, vi r, vi c) { vp v; rep(i, n) { if (r[i] <= c[i]) v.eb(r[i], c[i] + 1); else v.eb(c[i], r[i] + 1); } sort(all(v)); vi ls; int mx = 0; rep(i, n) if (chmax(mx, v[i].second)) ls.pb(i); int sz = ls.size(); vl s(sz), t(sz); rep(i, sz) { s[i] = v[ls[i]].first; t[i] = v[ls[i]].second; } vector<li_chao_tree> dp(k + 1, li_chao_tree(t)); rep(i, sz) { dp[1].add_line(-2 * s[0], s[0] * s[0]); } rep2(i, 1, sz) rep2(j, 1, k) { ll now = dp[j].get_min(i - 1); if (now == linf) continue; now += t[i - 1] * t[i - 1]; rep2(ni, i, sz) { ll lap = max(0LL, t[i - 1] - s[i]); dp[j + 1].add_line(-2 * s[i], now - lap * lap + s[i] * s[i]); } } ll ans = linf; rep2(i, 1, k + 1) chmin(ans, dp[i].get_min(sz - 1) + t.back() * t.back()); 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...