oj.uz

Submission #988392

# Submission time Handle Problem Language Result Execution time Memory
988392 2024-05-24T15:13:02 Z parlimoos Sure Bet (CEOI17_sure) C++14
100 / 100
 341 ms 3784 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define all(x) array<ll , x>
#define endl '\n'

int n;
vector<ll> a[2];

int getIn(){
    int res = 0;
    char d;
    cin >> d;
    while(d != '.'){
        res *= 10 , res += int(d - '0');
        cin >> d;
    }
    for(int i = 0 ; i < 4 ; i++){
        cin >> d;
        res *= 10 , res += int(d - '0');
    }
    return res;
}
bool jg(ll e){
    bool flg = (e == 0);
    for(ll i = 1 ; i <= n + n ; i++){
        auto itr = lb(a[0].bg() , a[0].end() , e + (i * 10000));
        if(itr == a[0].end()) continue;
        int inx = i - int(itr - a[0].bg()) - 1;
        if(inx > n or inx <= 0) continue;
        if(a[1][inx - 1] >= e + (i * 10000)) flg = 1;
    }
    return flg;
}
ll bs(){
    ll l = 0 , r = (1ll * 1e18);
    while(r - l - 1 > 1){
        ll c = l + (r - l - 1) / 2 + 1;
        if(jg(c)) l = c - 1;
        else r = c;
    }
    if(r - l - 1 == 1 and jg(l + 1)) return l + 1;
    return l;
}

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

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        a[0].pb(getIn()) , a[1].pb(getIn());
    }
    sort(a[0].bg() , a[0].end() , [](ll a , ll b){
        return (a > b);
    });
    sort(a[1].bg() , a[1].end() , [](ll a , ll b){
        return (a > b);
    });
    for(int i = 1 ; i < n ; i++) a[0][i] += a[0][i - 1] , a[1][i] += a[1][i - 1];
    ll o = bs();
    cout << o / 10000 << ".";
    o %= 10000 , cout << o / 1000;
    o %= 1000 , cout << o / 100;
    o %= 100 , cout << o / 10;
    o %= 10 , cout << o;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 2 ms 344 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 2 ms 344 KB Output is correct
17 Correct 341 ms 3524 KB Output is correct
18 Correct 327 ms 3524 KB Output is correct
19 Correct 330 ms 3524 KB Output is correct
20 Correct 308 ms 3524 KB Output is correct
21 Correct 222 ms 3756 KB Output is correct
22 Correct 341 ms 3524 KB Output is correct
23 Correct 333 ms 3528 KB Output is correct
24 Correct 329 ms 3524 KB Output is correct
25 Correct 309 ms 3524 KB Output is correct
26 Correct 216 ms 3784 KB Output is correct