제출 #791108

#제출 시각아이디문제언어결과실행 시간메모리
791108WLZAliens (IOI16_aliens)C++17
100 / 100
129 ms8588 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../debug.h" #else #define debug(...) 0 #endif using ii = pair<int, int>; using ll = long long; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; const ll LINF = (ll) 1e18; class convex_hull { private: vector<long long> a, b; vector<int> id; int ptr = 0; int bad(int l1, int l2, long long _a, long long _b) { if ((a[l1] == _a) && (b[l1] == _b)) return 1; return ((_b - b[l1]) * (a[l1] - a[l2]) > (b[l2] - b[l1]) * (a[l1] - _a)); } public: void add(long long _a, long long _b, int _id) { while ((int) a.size() >= 2 && bad((int) a.size() - 1, (int) a.size() - 2, _a, _b)) { a.pop_back(); b.pop_back(); id.pop_back(); } a.push_back(_a); b.push_back(_b); id.push_back(_id); } pair<int, long long> query(long long x) { if (ptr >= (int) a.size()) { ptr = (int) a.size() - 1; } while (ptr < (int) a.size() - 1 && a[ptr + 1] * x + b[ptr + 1] >= a[ptr] * x + b[ptr]) { ptr++; } return {id[ptr], a[ptr] * x + b[ptr]}; } }; pair<ll, int> solve(int n, int m, const vi &r, const vi &c, ll cost) { convex_hull ch; ch.add(-(-2 * r[0]), -((ll) r[0] * r[0] - 2 * r[0]), 0); for (int i = 1; i <= n; i++) { auto p = ch.query(c[i - 1]); ll best = -p.second + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1) + cost; if (i == n) return {best, p.first + 1}; ch.add(-(-2 * r[i]), -(best + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)), p.first + 1); } } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); ll lo = 0, hi = (1ll << 46); while (lo < hi) { ll mid = (lo + hi + 1) / 2; auto p = solve(n, m, r, c, mid); if (p.second >= k) lo = mid; else hi = mid - 1; } return solve(n, m, r, c, lo).first - k * lo; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'std::pair<long long int, int> solve(int, int, const vi&, const vi&, ll)':
aliens.cpp:53:15: warning: control reaches end of non-void function [-Wreturn-type]
   53 |   convex_hull ch;
      |               ^~
#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...