Submission #839037

#TimeUsernameProblemLanguageResultExecution timeMemory
839037LucaIlieCake 3 (JOI19_cake3)C++17
100 / 100
3391 ms17604 KiB
#include <bits/stdc++.h> using namespace std; struct ab { int a, b; }; struct event { int type, val, t; }; const int MAX_N = 2e5; const long long INF = 1e18; const int MAX_EVENTS = 2 * MAX_N; int m; int timee = 0; int nrEv = 0; long long sumA = 0; long long ans = -INF; ab v[MAX_N + 1]; event events[MAX_EVENTS]; multiset <int> s; void solve( int ll, int lr, int rl, int rr ) { if ( ll > lr || rl > rr || rr - ll + 1 < m ) return; int l = (ll + lr) / 2; long long answer = -INF; int bestR = rr; int t = timee; for ( int i = l; i <= lr && i < rl; i++ ) { s.insert( v[i].a ); sumA += v[i].a; events[nrEv++] = { 1, v[i].a, ++timee }; if ( s.size() > m ) { sumA -= *s.begin(); events[nrEv++] = { -1, *s.begin(), ++timee }; s.erase( s.begin() ); } } for ( int r = max( l, rl ); r <= rr; r++ ) { s.insert( v[r].a ); sumA += v[r].a; events[nrEv++] = { 1, v[r].a, ++timee }; if ( s.size() > m ) { sumA -= *s.begin(); events[nrEv++] = { -1, *s.begin(), ++timee }; s.erase( s.begin() ); } if ( s.size() >= m ) { if ( sumA - 2 * (v[r].b - v[l].b) > answer ) { answer = sumA - 2 * (v[r].b - v[l].b); bestR = r; } } } while ( nrEv > 0 && events[nrEv - 1].t > t ) { int x = events[nrEv - 1].val; if ( events[nrEv - 1].type == 1 ) { s.erase( s.find( x ) ); sumA -= x; } else { s.insert( x ); sumA += x; } nrEv--; } for ( int i = min( rl - 1, lr ); i >= l; i-- ) { s.insert( v[i].a ); sumA += v[i].a; events[nrEv++] = { 1, v[i].a, ++timee }; if ( s.size() > m ) { sumA -= *s.begin(); events[nrEv++] = { -1, *s.begin(), ++timee }; s.erase( s.begin() ); } } solve( ll, l - 1, rl, bestR ); while ( nrEv > 0 && events[nrEv - 1].t > t ) { int x = events[nrEv - 1].val; if ( events[nrEv - 1].type == 1 ) { s.erase( s.find( x ) ); sumA -= x; } else { s.insert( x ); sumA += x; } nrEv--; } for ( int i = max( rl, lr + 1 ); i < bestR; i++ ) { s.insert( v[i].a ); sumA += v[i].a; events[nrEv++] = { 1, v[i].a, ++timee }; if ( s.size() > m ) { sumA -= *s.begin(); events[nrEv++] = { -1, *s.begin(), ++timee }; s.erase( s.begin() ); } } solve( l + 1, lr, bestR, rr ); while ( nrEv > 0 && events[nrEv - 1].t > t ) { int x = events[nrEv - 1].val; if ( events[nrEv - 1].type == 1 ) { s.erase( s.find( x ) ); sumA -= x; } else { s.insert( x ); sumA += x; } nrEv--; } ans = max( ans, answer ); } int main() { int n; cin.tie( NULL ); ios_base::sync_with_stdio( false ); cin >> n >> m; for ( int i = 1; i <= n; i++ ) cin >> v[i].a >> v[i].b; sort( v + 1, v + 1 + n, []( ab x, ab y ) { return x.b < y.b; } ); solve( 1, n, 1, n ); cout << ans; return 0; }

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:40:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         if ( s.size() > m ) {
      |              ~~~~~~~~~^~~
cake3.cpp:51:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         if ( s.size() > m ) {
      |              ~~~~~~~~~^~~
cake3.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         if ( s.size() >= m ) {
      |              ~~~~~~~~~^~~~
cake3.cpp:80:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if ( s.size() > m ) {
      |              ~~~~~~~~~^~~
cake3.cpp:103:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |         if ( s.size() > m ) {
      |              ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...