oj.uz

Submission #802133

# Submission time Handle Problem Language Result Execution time Memory
802133 2023-08-02T10:12:36 Z vjudge1 Sure Bet (CEOI17_sure) C++11
100 / 100
 88 ms 5760 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <deque>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <iomanip>
using namespace std;
using lli = long long;
using ldb = long double;
const int maxN = 1e5;
ldb a[maxN + 1];
ldb b[maxN + 1];
ldb ps[maxN + 1];
int n;

ldb Calc(ldb resa, ldb resb, int pb)
{
    if (resb >= resa)
        return resb;
    int low = pb;
    int high = n;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (resa - (mid - pb + 1) >= resb + ps[mid] - ps[pb - 1] - (mid - pb + 1))
            low = mid + 1;
        else
            high = mid - 1;
    }
    --low;
    resa -= (low - pb + 1);
    resb += ps[low] - ps[pb - 1] - (low - pb + 1);
    ldb res = resb;
    if (low < n)
        res = max(res, resa - 1);
    return res;
}

int main()
{
#ifdef LeMinhDuc
    freopen("inp.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    int pa = 1, pb = 1;
    ldb resa = 0, resb = 0;
    ldb res = min(resa, resb);
    ps[0] = 0;
    for (int i = 1; i <= n; ++i)
        ps[i] = ps[i - 1] + b[i];
    res = max(res, Calc(resa, resb, pb));
    for (int i = pa; i <= n; ++i)
    {
        resa += a[i] - 1;
        --resb;
        res = max(res, Calc(resa, resb, pb));
    }
    cout << fixed << setprecision(4) << res;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 88 ms 5632 KB Output is correct
18 Correct 77 ms 5524 KB Output is correct
19 Correct 80 ms 5760 KB Output is correct
20 Correct 82 ms 5544 KB Output is correct
21 Correct 83 ms 5628 KB Output is correct
22 Correct 78 ms 5580 KB Output is correct
23 Correct 78 ms 5620 KB Output is correct
24 Correct 80 ms 5624 KB Output is correct
25 Correct 84 ms 5524 KB Output is correct
26 Correct 85 ms 5532 KB Output is correct