oj.uz

Submission #681398

# Submission time Handle Problem Language Result Execution time Memory
681398 2023-01-13T02:15:03 Z vjudge1 Sure Bet (CEOI17_sure) C++14
0 / 100
 0 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<double, double> pdd;

void print() {cerr << '\n';} template <typename T1, typename... T2>
void print(const T1 &a, const T2 &...b) { cerr << a << ' ', print(b...); }

const int N = 1e5;
const int mod = 1e9 + 7;

pdd a[N];
double res = 0;
double t1[N], t2[N];
int n;

bool cmp(const pdd &a, const pdd &b)
{
    return a.F - a.S > b.F - b.S;
}

void calc(int x, int y)
{
    int total = x + y;
    t1[0] = t2[0] = t1[n + 1] = t2[n + 1] = 0;
    priority_queue<double, vector<double>, greater<double>> q;
    for(int i = 1; i <= n; i++)
    {
        t1[i] = t1[i - 1] + a[i].F;
        q.push(a[i].F);
        if((int)q.size() > x)
        {
            t1[i] -= q.top();
            q.pop();
        }
    }
    while(q.size()) q.pop();
    for(int i = n; i >= 1; i--)
    {
        t2[i] = t2[i + 1] + a[i].S;
        q.push(a[i].S);
        if((int)q.size() > y)
        {
            t2[i] -= q.top();
            q.pop();
        }
    }
    double tmp = -1e18;
    for(int i = x; i + y <= n; i++)
    {
        res = max(res, min(t1[i] - total, t2[i + 1] - total));
        tmp = max(tmp, min(t1[i] - total, t2[i + 1] - total));
    }
}


void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i].F >> a[i].S;
    sort(a + 1, a + 1 + n, cmp);
    for(int num = 1; num <= n; num++)
        for(int i = 0; i <= num; i++)
            calc(i, num - i);
    cout << setprecision(4) << fixed << res;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 40.0

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