제출 #578430

#제출 시각아이디문제언어결과실행 시간메모리
578430vladislav11Sure Bet (CEOI17_sure)C++14
100 / 100
88 ms3824 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
vector<double> a, b;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for ( int i=0; i<n; i++ )
    {
        double dl, dr;
        cin >> dl >> dr;

        a.push_back( dl );
        b.push_back( dr );
    }

    sort( a.begin(), a.end(), greater<double>() );
    sort( b.begin(), b.end(), greater<double>() );

    /*for ( auto& el : a )
        cout << el << ' ';
    cout << '\n';

    for ( auto& el : b )
        cout << el << ' ';
    cout << '\n';*/

    double ans = 0;

    double cur1 = 0;
    double cur2 = 0;
    int j = -1;

    for ( int i=0; i<n; i++ )
    {
        cur1 += a[i];

        while ( j+1 < n && min( cur1 - ( i+1 + j+1 ), cur2 - ( i+1 + j+1 ) ) < min( cur1 - ( i+1 + j+2 ), cur2+b[j+1] - ( i+1 + j+2 ) ) )
        {
            j++;
            cur2 += b[j];
        }

        //cout << "for " << i << " - " << j << ": " << cur1 << ' ' << cur2 << ' ' << min( cur1 - ( i+1 + j+1 ), cur2 - ( i+1 + j+1 ) ) << '\n';

        ans = max( ans, min( cur1 - ( i+1 + j+1 ), cur2 - ( i+1 + j+1 ) ) );
    }

    cout << fixed << setprecision(4);
    cout << ans;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...