oj.uz

Submission #498345

# Submission time Handle Problem Language Result Execution time Memory
498345 2021-12-25T04:32:15 Z Nalrimet Sure Bet (CEOI17_sure) C++17
60 / 100
 2000 ms 6328 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first

//const int inf = 1e18;
const int N = 100005;

int n, y;
long double a[N], b[N], pref[N], suma, ans;

ld f(int x){
//    cout << x << ' ' << y << ' ' << pref[x] << ' ' << suma << '\n';
    return min(pref[x], suma) - x - y;
}

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

    cin >> n;

    for(int i = 1; i <= n; ++i){
        cin >> a[i] >> b[i];
    }

    sort(a + 1, a + 1 + n, greater<ld>());
    sort(b + 1, b + 1 + n, greater<ld>());


    for(int i = 0; i <= n; ++i){
        pref[i] += pref[i - 1] + b[i];
    }

    for(int i = 0; i <= n; ++i){
//        cout << a[i] << ' ';
        suma += a[i];
        y = i;
//        for(int j = 0; j <= n; ++j){
//        }
        int l = 0, r = n;
//        ld = eps = 1e-9
        while(l < r){
//            cout << l << ' ' << r << '\n';
            int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
//            cout << m1 << ' ' << m2 << ' ' << f(m1) << ' ' << f(m2) << '\n';
            if(f(m1) < f(m2))
                l = m1 + 1;
            else if(f(m1) > f(m2))
                r = m2 - 1;
            else{
                l = m1;
                r = m2;
            }
        }
        ans = max(ans, f(l));
    }

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

Compilation message

sure.cpp:22:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 |  main(){
      |  ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 170 ms 4972 KB Output is correct
18 Correct 182 ms 6328 KB Output is correct
19 Execution timed out 2039 ms 6248 KB Time limit exceeded
20 Halted 0 ms 0 KB -