Submission #1011363

#TimeUsernameProblemLanguageResultExecution timeMemory
1011363NValchanovSure Bet (CEOI17_sure)C++17
100 / 100
54 ms3756 KiB
#include<bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const ll MAXN = 1e6 + 10;
 
ll n;
double a[MAXN];
double b[MAXN];
double max_win;
 
void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
}
 
bool cmp(double x, double y)
{
    return x > y;
}
 
void solve()
{
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);
 
    ll idxa = 1;
    ll idxb = 1;
    double suma = 0.0;
    double sumb = 0.0;
 
    while(idxa <= n)
    {
        suma += a[idxa++];
 
        while(idxb <= n && min(suma - idxb + 1, sumb - idxa + 1) < min(suma - idxb, sumb + b[idxb] - idxa + 1))
        {
            sumb += b[idxb];
            idxb++;
        }
 
        max_win = max(max_win, min(suma - idxb + 1, sumb - idxa + 1));
    }
 
    cout << fixed << setprecision(4) << max_win << endl;
 
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
 
	read();
	solve();
 
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...