Submission #800052

#TimeUsernameProblemLanguageResultExecution timeMemory
800052NguyenQuangKhaiSure Bet (CEOI17_sure)C++17
100 / 100
75 ms3444 KiB
#include <bits/stdc++.h>
#define taskname "surebet"
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef unsigned long long ull;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define es erase
#define is insert
#define all(x) x.begin(), x.end()
#define EL printf("\n")
#define sz(A) (int) A.size()
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Os")
//#pragma GCC target ("avx2")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
priority_queue <int,vector<int>,greater<int> > pq;
int n ;
const int maxn = 1e5+13;
long double a[maxn], b[maxn];
bool cmp (int x , int y)
{
    return x > y;
}
void readInput()
{
    cin>>n;
    for(int i=1 ; i<=n ; ++i) cin>>a[i]>>b[i];
    sort(a+1, a+1+n );
    sort(b+1, b+1+n );
    bool ok = false;
    long double ans = 0;
    int cnt = 0;
    long double suma = 0;
    long double sumb = 0;
    int k1 = n;
    int k2 = n;
    while(true)
    {
        if(k1 == 0 && k2 == 0) break;
        if(k1 == 0)
        {
            sumb += b[k2];
            k2--;
            cnt++;
        }
        else if(k2 == 0)
        {
             suma += a[k1];
            k1--;
            cnt++;
        }
        else if(suma<sumb )
        {
            suma += a[k1];
            k1--;
            cnt++;
        }
        else if( suma > sumb)
        {
            sumb += b[k2];
            k2--;
            cnt++;
        }
        else if(suma == sumb)
        {
            if(k2 == 0 || a[k1] > b[k2])
            {
                suma += a[k1];
                k1--;
                cnt++;
            }
            else if(k1 == 0 || a[k1] <= b[k2])
            {
                sumb += b[k2];
                k2--;
                cnt++;
            }
        }
        long double res = min(suma - cnt , sumb - cnt);
        ans = max(ans , res);
    }
    cout<<fixed << setprecision(4) <<ans;
}
void init()
{

}
void solve()
{

}
void print()
{

}
int main()
{
    faster
//    freopen(taskname".INP","r",stdin);
//    freopen(taskname".OUT","w",stdout);
    readInput();
    solve();
    print();
    return 0;
}
/* test







*/

Compilation message (stderr)

sure.cpp: In function 'void readInput()':
sure.cpp:40:10: warning: unused variable 'ok' [-Wunused-variable]
   40 |     bool ok = false;
      |          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...