oj.uz

Submission #800971

# Submission time Handle Problem Language Result Execution time Memory
800971 2023-08-02T03:10:51 Z vjudge1 Sure Bet (CEOI17_sure) C++11
0 / 100
 1 ms 340 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;
    while (pa <= n && a[pa] >= 2 && b[pb] >= 2)
    {
        resa += a[pa] - 2;
        resb += b[pb] - 2;
        ++pa;
        ++pb;
    }
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -