Submission #838757

#TimeUsernameProblemLanguageResultExecution timeMemory
838757beabossCake 3 (JOI19_cake3)C++14
24 / 100
4051 ms33628 KiB
// Source: https://oj.uz/problem/view/JOI19_cake3 // #include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<ll, ll> pii; typedef vector<pii> vpii; typedef vector<ll> vi; #define FOR(i, a, b) for (ll i = (a); i<b; i++) const ll N = 2e5 + 10; // const ll N = 1e5; #define lc i << 1 #define rc (i << 1) + 1 pair<ll, vi> st[4 * N]; ll n, m; pii inp[N]; pair<ll, vi> comb(pair<ll, vi> a1, pair<ll, vi> b1) { // MODIFY COMBINER FUNCTION // combine two sorted vectors ll i = 0; ll j = 0; vi a = a1.s; vi b = b1.s; ll sum = 0; vi vals; FOR(_, 0, m) { if (i == a.size() && j == b.size()) break; if (i == a.size()) { vals.pb(b[j]); sum+= b[j]; j++; } else if (j == b.size()) { vals.pb(a[i]); sum+= a[i]; i++; } else if (a[i] > b[j]) { vals.pb(a[i]); sum+= a[i]; i++; } else { vals.pb(b[j]); sum+= b[j]; j++; } } return {sum, vals}; } void up(ll i) { st[i] = comb(st[lc], st[rc]); } void update(ll ind, ll val, ll i = 1, ll l = 0, ll r = n) { // update pos ind with value val if (l >= r) return; if (r - l == 1) { st[i] = {val, {val}}; return; } ll m = (l + r)/2; if (m > ind) update(ind, val, lc, l, m); // contained in left child else update(ind, val, rc, m, r); // contained in right child up(i); // update current index } pair<ll, vi> query(ll ql, ll qr, ll i = 1, ll l = 0, ll r = n) { // query from [ql, qr) if (l >= r) return {0, {}}; // identity if (ql <= l && qr >= r) { // fully contained return st[i]; } if (r - l == 1) return {0, {}}; // leaf node ll m = (l + r)/2; pair<ll, vi> acc = {0, {}}; // SET DEFAULT VALUE if (m >= ql) acc = comb(query(ql, qr, lc, l, m), acc); if (m <= qr) acc = comb(acc, query(ql, qr, rc, m, r)); return acc; } ll ans = -1e18; void solve(ll ia, ll ib, ll ja, ll jb) { // solves range [ia, ib) assuming the previous DP can be from [ja, jb] if (ia >= ib) return; ll i = (ia + ib) / 2; // if (i-m+1 < ja) { // solve(i + 1, ib, ja, jb); // return; // to few numbers // } assert(i - m + 1 >= ja); ll arg_j = 0; ll opt = -1e18; for (ll j = ja; j <= min(i-m+1, jb); j++) { ll v = query(j, i+1).f - 2 * (inp[i].f - inp[j].f); // cout << i << j << v << endl; if (v > opt) { arg_j = j; opt = v; } } ans = max(ans, opt); // solve(ia, i, 0, n); // solve(i + 1, ib, 0, n); solve(ia, i, ja, arg_j); solve(max(arg_j + m - 1, i+1), ib, arg_j, jb); // ll sum = 0; // ll opt = 0; // multiset<ll> vals; // for (ll j = i; j > i-m; j--) { // vals.insert(inp[j].s); // sum+=inp[j].s; // } // opt = sum - 2ll * (inp[i].f - inp[i-m+1].f); // for (ll j = i-m; j >= ja; j--) { // sum += inp[j].s; // vals.insert(inp[j].s); // sum -= *vals.begin(); // vals.erase(vals.begin()); // ll v = sum - 2ll * (inp[i].f - inp[j].f); // if (v > opt) { // arg_j = j; // opt=v; // } // } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; FOR(i, 0, n) cin >> inp[i].s >> inp[i].f; sort(inp, inp + n); FOR(i, 0, n) update(i, inp[i].s); // cout << query(0, 3).f << endl; solve(m-1, n, 0, n); cout << ans << endl; }

Compilation message (stderr)

cake3.cpp: In function 'std::pair<long long int, std::vector<long long int> > comb(std::pair<long long int, std::vector<long long int> >, std::pair<long long int, std::vector<long long int> >)':
cake3.cpp:45:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if (i == a.size() && j == b.size()) break;
      |       ~~^~~~~~~~~~~
cake3.cpp:45:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if (i == a.size() && j == b.size()) break;
      |                        ~~^~~~~~~~~~~
cake3.cpp:46:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (i == a.size()) {
      |       ~~^~~~~~~~~~~
cake3.cpp:50:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   } else if (j == b.size()) {
      |              ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...