Submission #498356

#TimeUsernameProblemLanguageResultExecution timeMemory
498356vinnipuh01Sure Bet (CEOI17_sure)C++17
100 / 100
203 ms8524 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> #define double long double using namespace std; const long long oo = 1000000000000000000; double sum, ans = 0, mx = 0, mn, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen ( "sum.in", "r", stdin ) */ int n; double a[ 100001 ], b[ 100001 ]; vector <double> v, vv; double f( int mask, int o, double sum, double ans, double col ) { double mxx = min( sum - col, ans - col ); for ( int i = o; i < n; i ++ ) { if ( !( mask & ( 1 << i ) ) ) { mask |= ( 1 << i ); col ++; sum += a[ i ]; mxx = max( mxx, f( mask, i + 1, sum, ans, col ) ); sum -= a[ i ]; ans += b[ i ]; mxx = max( mxx, f( mask, i + 1, sum, ans, col ) ); col --; ans -= b[ i ]; col += 2; ans += b[ i ]; sum += a[ i ]; mxx = max( mxx, f( mask, i + 1, sum, ans, col ) ); col -= 2; ans -= b[ i ]; sum -= a[ i ]; mask ^= ( 1 << i ); } } return mxx; } double p[ 100001 ]; double f( int x ) { return min( sum - pos, p[ x ] - pos ); } int main () { cin >> n; for ( int i = 1; i <= n; i ++ ) { cin >> a[ i ] >> b[ i ]; v.push_back( a[ i ] ); vv.push_back( b[ i ] ); } sort( v.begin(), v.end() ); sort( vv.begin(), vv.end() ); reverse( v.begin(), v.end() ); reverse( vv.begin(), vv.end() ); for ( int i = 0; i < vv.size(); i ++ ) p[ i + 1 ] = vv[ i ] + p[ i ]; sum = num = ans = mx = 0; int l, r, mid2, mid1; for ( int i = 0; i < v.size(); i ++ ) { sum += v[ i ]; ans = i + 1; mx = max( mx, min( sum - ans, -ans ) ); l = 1; r = vv.size(); while ( r - l > 2 ) { mid1 = l + ( r - l ) / 3; mid2 = r - ( r - l ) / 3; pos = mid1 + i + 1; ans = f( mid1 ); pos = mid2 + i + 1; mn = f( mid2 ); if ( ans < mn ) l = mid1; else r = mid2; } pos = r + i + 1; ans = f( r ); pos = i + l + 1; mn = f( l ); if ( ans >= mn ) l = r; pos = ( r - 1 ) + i + 1; ans = f( r - 1 ); pos = l + i + 1; mn = f( l ); if ( ans >= mn ) l = r - 1; pos = l + i + 1; mx = max( mx, f( l ) ); } cout << fixed << setprecision(4) << mx; }

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for ( int i = 0; i < vv.size(); i ++ )
      |                   ~~^~~~~~~~~~~
sure.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for ( int i = 0; i < v.size(); i ++ ) {
      |                   ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...