제출 #947349

#제출 시각아이디문제언어결과실행 시간메모리
947349caterpillowCake 3 (JOI19_cake3)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll 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 */ 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; } }; const int sz = 1 << 18; vt<ptr> roots; ptr pull(ptr l, ptr r) { ptr res = new Node(l->val + r->val, l->cnt + r->cnt); res->l = l; res->r = r; return res; } 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 pull(update(n->l, val, i, l, m), n->r); else return pull(n->l, update(n->r, val, i, m + 1, r)); } ll walk(ptr ln, ptr rn, int k, int l = 0, int r = sz - 1) { if (l == r) return k ? rn->val - ln->val : 0ll; int m = (l + r) / 2; int rhs = rn->r->cnt - ln->r->cnt; if (rhs >= k) return walk(ln->r, rn->r, k, m + 1, r); // go right else return walk(ln->l, rn->l, k - rhs, l, m) + rn->r->val - ln->r->val; } 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 0ll; int m = (l + r) / 2; pl best = {0, -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; roots.resize(n + 1); 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:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...