Submission #572501

#	Time	Username	Problem	Language	Result	Execution time	Memory
572501		urosk	Sure Bet (CEOI17_sure)	C++14	100 / 100	94 ms	6752 KiB

sure

//https://oj.uz/problem/view/CEOI17_sure
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 100005
ll n;
vector<ld> v,w;
bool cmp(ld x,ld y){return x>y;}
ld reshi(vector<ld> a,vector<ld> b){
    ld ans = 0;
    ld suma = 0;
    ld sumb = 0;
    ll j = 1;
    for(ll i = 1;i<=n;i++){
        suma+=a[i];
        while(j<=n&&sumb+b[j]<=suma){
            sumb+=b[j];
            ans = max(ans,sumb-i-j);
            j++;
        }
    }
    return ans;
}
int main(){
	daj_mi_malo_vremena
    cin >> n;
    v.resize(n+1);
    w.resize(n+1);
    for(ll i = 1;i<=n;i++){
        cin >> v[i] >> w[i];
    }
    sort(v.begin()+1,v.end(),cmp);
    sort(w.begin()+1,w.end(),cmp);
    ld ans = max(reshi(v,w),reshi(w,v));
    cout<<fixed<<setprecision(4);
    cout<<ans<<endl;
    return 0;
}
/*
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5
*/

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40