제출 #1077401

#제출 시각아이디문제언어결과실행 시간메모리
1077401bleahbleahTricks of the Trade (CEOI23_trade)C++17
10 / 100
8064 ms19232 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 25e4 + 5; int K; const ll inf = 1e18; struct KthHeap { multiset<int> outside, inside; void repair() { while(sz(inside) > K) { int x = *inside.begin(); inside.erase(inside.find(x)); outside.insert(x); sum -= x; } while(sz(inside) < K && sz(outside)) { int x = *outside.rbegin(); outside.erase(outside.find(x)); inside.insert(x); sum += x; } while(sz(inside) && sz(outside) && *inside.begin() < *outside.rbegin()) { int x = *outside.rbegin(), y = *inside.begin(); outside.erase(outside.find(x)); inside.erase(inside.find(y)); outside.emplace(y); inside.emplace(x); sum += x - y; } return; } void erase(int x) { if(outside.find(x) != outside.end()) outside.erase(outside.find(x)); else if(inside.find(x) != inside.end()) inside.erase(inside.find(x)), sum -= x; else assert(false); repair(); } void insert(int x) { outside.emplace(x); repair(); } ll query() { repair(); if(sz(inside) < K) return -inf; return sum; } private: ll sum = 0; }; ll dp[nmax]; ll spart[nmax]; ll v[nmax]; ll S(int l, int r) { return spart[r] - spart[l - 1]; } namespace DivideM { int bestcut[nmax]; KthHeap hint; void divide(int l, int r) { if(l + 1 == r) return; int optl = bestcut[l], optr = bestcut[r]; int mid = l + r >> 1; if(r <= optl) { for(int i = mid; i < r; i++) hint.insert(v[i]); ll best = hint.query() - S(mid, optl); int atr = optl; for(int i = optl + 1; i <= optr; i++) { hint.insert(v[i]); if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i); } bestcut[mid] = atr, dp[mid] = best; if(atr - mid + 1 == K) { int SA = S(mid, atr), SB = 0; for(int i = mid; i <= atr; i++) SB += v[i]; } for(int i = optl + 1; i <= optr; i++) hint.erase(v[i]); divide(l, mid); for(int i = mid; i < r; i++) hint.erase(v[i]); for(int i = optl + 1; i <= atr; i++) hint.insert(v[i]); divide(mid, r); for(int i = optl + 1; i <= atr; i++) hint.erase(v[i]); } else { int border = max(mid - 1, optl); for(int i = mid; i <= border; i++) hint.insert(v[i]); ll best = hint.query() - S(mid, border), atr = border; for(int i = border + 1; i <= optr; i++) { hint.insert(v[i]); if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i); } bestcut[mid] = atr, dp[mid] = best; for(int i = optr; i > border; i--) hint.erase(v[i]); divide(l, mid); for(int i = mid; i <= border; i++) hint.erase(v[i]); for(int i = r; i <= atr; i++) hint.insert(v[i]); divide(mid, r); for(int i = r; i <= atr; i++) hint.erase(v[i]); } } } namespace Dividem { int bestcut[nmax]; KthHeap hint; void divide(int l, int r) { if(l + 1 == r) return; int optl = bestcut[l], optr = bestcut[r]; int mid = l + r >> 1; if(r <= optl) { for(int i = mid; i < r; i++) hint.insert(v[i]); ll best = hint.query() - S(mid, optl); int atr = optl; for(int i = optl + 1; i <= optr; i++) { hint.insert(v[i]); if(hint.query() - S(mid, i) > best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i); } bestcut[mid] = atr, dp[mid] = best; if(atr - mid + 1 == K) { int SA = S(mid, atr), SB = 0; for(int i = mid; i <= atr; i++) SB += v[i]; } for(int i = optl + 1; i <= optr; i++) hint.erase(v[i]); divide(l, mid); for(int i = mid; i < r; i++) hint.erase(v[i]); for(int i = optl + 1; i <= atr; i++) hint.insert(v[i]); divide(mid, r); for(int i = optl + 1; i <= atr; i++) hint.erase(v[i]); } else { int border = max(mid - 1, optl); for(int i = mid; i <= border; i++) hint.insert(v[i]); ll best = hint.query() - S(mid, border), atr = border; for(int i = border + 1; i <= optr; i++) { hint.insert(v[i]); if(hint.query() - S(mid, i) > best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i); } bestcut[mid] = atr, dp[mid] = best; for(int i = optr; i > border; i--) hint.erase(v[i]); divide(l, mid); for(int i = mid; i <= border; i++) hint.erase(v[i]); for(int i = r; i <= atr; i++) hint.insert(v[i]); divide(mid, r); for(int i = r; i <= atr; i++) hint.erase(v[i]); } } } signed main() { cin.tie(0) -> sync_with_stdio(0); int n; cin >> n >> K; for(int i = 1; i <= n; i++) { cin >> spart[i]; spart[i] += spart[i - 1]; } for(int i = 1; i <= n; i++) cin >> v[i]; DivideM::bestcut[0] = Dividem::bestcut[0] = 0; DivideM::bestcut[n - K + 2] = Dividem::bestcut[n - K + 2] = n; DivideM::divide(0, n - K + 2); Dividem::divide(0, n - K + 2); ll mx = -inf; vector<int> possible(n + 1); for(int i = 1; i <= n - K + 1; i++) mx = max(mx, dp[i]); cout << mx << '\n'; auto cmp = [&](int a, int b) { return (v[a] < v[b] || (v[a] == v[b] && a < b)); }; set<int, decltype(cmp)> inside(cmp), outside(cmp); int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf; for(int i = 1; i <= n; i++) { if(dp[i] != mx) continue; set<int, decltype(cmp)> kth(cmp); for(int j = i; j < Dividem::bestcut[i]; j++) { kth.emplace(j); } auto repair = [&]() { while(sz(kth) > K && v[*kth.begin()] < v[*next(kth.begin())]) { kth.erase(kth.begin()); } return; }; for(int j = Dividem::bestcut[i]; j <= Dividem::bestcut[i]; j++) { kth.emplace(j); repair(); for(auto x : kth) possible[x] = 1; } } for(int i = 1; i <= n; i++) cout << possible[i]; cout << '\n'; } /** Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen -- */

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

trade.cpp: In function 'void DivideM::divide(ll, ll)':
trade.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:93:17: warning: unused variable 'SA' [-Wunused-variable]
   93 |             int SA = S(mid, atr), SB = 0;
      |                 ^~
trade.cpp: In function 'void Dividem::divide(ll, ll)':
trade.cpp:135:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:146:17: warning: unused variable 'SA' [-Wunused-variable]
  146 |             int SA = S(mid, atr), SB = 0;
      |                 ^~
trade.cpp: In function 'int main()':
trade.cpp:207:8: warning: unused variable 'criteriaIL' [-Wunused-variable]
  207 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |        ^~~~~~~~~~
trade.cpp:207:28: warning: unused variable 'criteriaIR' [-Wunused-variable]
  207 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |                            ^~~~~~~~~~
trade.cpp:207:45: warning: unused variable 'criteriaV' [-Wunused-variable]
  207 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |                                             ^~~~~~~~~
#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...