제출 #947351

#제출 시각아이디문제언어결과실행 시간메모리
947351caterpillowCake 3 (JOI19_cake3)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<ll,ll>; #define vt vector #define f first #define s second #define all(x) x.begin(), x.end() #define pb push_back #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i) #define F0R(i, b) FOR(i, 0, b) #define endl '\n' #define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0) const ll INF = 1e18; /* as l increases, the optimal r also increases */ const int sz = 1 << 18; using ptr = struct Node*; struct Node { ll val; int cnt; ptr l, r; Node(ll _val, int _cnt) { val = _val; cnt = _cnt; l = r = 0; } Node(ptr _l, ptr _r) { l = _l; r = _r; val = cnt = 0; if (l) val += l->val, cnt += l->cnt; if (r) val += r->val, cnt += r->cnt; } }; ptr update(ptr n, ll val, int i, int l = 0, int r = sz - 1) { if (l == r) return new Node(val, 1); int m = (l + r) / 2; if (i <= m) return new Node(update(n->l, val, i, l, m), n->r); else return new Node(n->l, update(n->r, val, i, m + 1, r)); } ll walk(ptr l, ptr r, int k, int lo = 0, int hi = sz - 1) { // sum of k largest if (lo == hi) return r->val - l->val; int m = (lo + hi) / 2; int rhs = r->r->cnt - l->r->cnt; if (rhs >= k) return walk(l->r, r->r, k, m + 1, hi); else return walk(l->l, r->l, k - rhs, lo, m) + r->r->val - l->r->val; } ptr roots[sz]; int n, k; vt<pl> cakes; ll query(int l, int r) { if (l > r) return 0ll; return walk(roots[l], roots[r + 1], k - 2); } ll dnc(int l, int r, int lo, int hi) { if (l > r) return -INF; int m = (l + r) / 2; pl best = {-INF, -1}; FOR (i, lo, hi + 1) { if (i - m + 1 < k) continue; ll val = query(m + 1, i - 1) - (cakes[i].f - cakes[m].f) + cakes[i].s + cakes[m].s; best = max(best, pl{val, i}); } return max({best.f, dnc(l, m - 1, lo, best.s), dnc(m + 1, r, best.s, hi)}); } main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k; cakes.resize(n); // colour, value F0R (i, n) cin >> cakes[i].s >> cakes[i].f, cakes[i].f *= 2; sort(all(cakes)); vt<pl> sorted(n); F0R (i, n) sorted[i] = {cakes[i].s, i}; sort(all(sorted)); vt<int> rind(n); F0R (i, n) rind[sorted[i].s] = i; ptr root = new Node(0, 0); roots[0] = root->l = root->r = root; F0R (i, n) { roots[i + 1] = update(roots[i], cakes[i].s, rind[i]); } cout << dnc(0, n - 1, 0, n - 1) << endl; }

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

cake3.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...