Submission #1069622

#TimeUsernameProblemLanguageResultExecution timeMemory
1069622GrindMachineTricks of the Trade (CEOI23_trade)C++17
10 / 100
8089 ms21372 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif /* refs: https://codeforces.com/blog/entry/98663 (max+ convolution tutorial) https://judge.yosupo.jp/submission/166484 (max+ convolution implementation) */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; vector<pll> max_conv(vector<ll> a, vector<pll> b){ // a = concave, b = arbitrary ll n = sz(a), m = sz(b); vector<pll> res(n+m-1,{-inf2,-inf2}); rep(i,n){ rep(j,m){ amax(res[i+j],{b[j].ff+a[i],b[j].ss}); } } return res; // vector<ll> res(n+m-1,-inf2); // auto go = [&](ll l, ll r, ll optl, ll optr, auto &&go) -> void{ // if(l > r) return; // ll mid = (l+r) >> 1; // ll best = -inf2, optm = -1; // for(int j = optl; j <= optr; ++j){ // ll i = mid-j; // if(i >= 0 and i < n){ // ll val = a[i]+b[j]; // if(val > best){ // best = val; // optm = j; // } // } // } // res[mid] = best; // go(l,mid-1,optl,optm,go); // go(mid+1,r,optm,optr,go); // }; // go(0,n+m-2,0,m-1,go); // return res; } void solve(int test_case) { ll n,k; cin >> n >> k; vector<ll> a(n+5), b(n+5); rep1(i,n) cin >> a[i]; rep1(i,n) cin >> b[i]; ll ans = -inf2; vector<pll> segs; auto upd = [&](ll l, ll r, ll v){ if(v > ans){ ans = v; segs.clear(); segs.pb({l,r}); } else if(v == ans){ segs.pb({l,r}); } }; auto go = [&](ll l, ll r, auto &&go) -> pair<vector<pll>,vector<pll>>{ if(l > r) return {{{0,0}},{{0,0}}}; if(l == r){ vector<pll> v = {{0,0},{-a[l]+b[l],1}}; return {v,v}; } ll mid = (l+r) >> 1; auto [lp,ls] = go(l,mid,go); auto [rp,rs] = go(mid+1,r,go); ll siz = r-l+1; vector<pll> cp(siz+1,{-inf2,-inf2}), cs(siz+1,{-inf2,-inf2}); rep(i,sz(lp)) amax(cp[i],lp[i]); rep(i,sz(rs)) amax(cs[i],rs[i]); { vector<ll> vals; ll sum = 0; for(int i = l; i <= mid; ++i){ sum -= a[i]; vals.pb(b[i]); } sort(rall(vals)); vals.insert(vals.begin(),sum); rep1(i,sz(vals)-1) vals[i] += vals[i-1]; auto res = max_conv(vals,rp); rep(i,sz(res)) res[i].ss += mid-l+1; rep(i,sz(res)) amax(cp[i],res[i]); } { vector<ll> vals; ll sum = 0; for(int i = mid+1; i <= r; ++i){ sum -= a[i]; vals.pb(b[i]); } sort(rall(vals)); vals.insert(vals.begin(),sum); rep1(i,sz(vals)-1) vals[i] += vals[i-1]; auto res = max_conv(vals,ls); rep(i,sz(res)) res[i].ss += r-mid; rep(i,sz(res)) amax(cs[i],res[i]); } if(k < sz(cp)) upd(l,l+cp[k].ss-1,cp[k].ff); if(k < sz(cs)) upd(r-cs[k].ss+1,r,cs[k].ff); rep(j,sz(ls)){ ll p = k-j; if(p >= 0 and p < sz(rp)){ ll lx = mid-ls[j].ss+1; ll rx = mid+1+rp[p].ss-1; ll val = ls[j].ff+rp[p].ff; upd(mid-ls[j].ss+1,mid+1+rp[p].ss-1,ls[j].ff+rp[p].ff); } } rep1(i,sz(cp)-1) assert(cp[i].ss >= cp[i-1].ss); rep1(i,sz(cs)-1) assert(cs[i].ss >= cs[i-1].ss); return {cp,cs}; }; go(1,n,go); cout << ans << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

Compilation message (stderr)

trade.cpp: In instantiation of 'solve(int)::<lambda(ll, ll, auto:23&&)> [with auto:23 = solve(int)::<lambda(ll, ll, auto:23&&)>&; ll = long long int]':
trade.cpp:190:14:   required from here
trade.cpp:177:20: warning: unused variable 'lx' [-Wunused-variable]
  177 |                 ll lx = mid-ls[j].ss+1;
      |                    ^~
trade.cpp:178:20: warning: unused variable 'rx' [-Wunused-variable]
  178 |                 ll rx = mid+1+rp[p].ss-1;
      |                    ^~
trade.cpp:179:20: warning: unused variable 'val' [-Wunused-variable]
  179 |                 ll val = ls[j].ff+rp[p].ff;
      |                    ^~~
#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...