oj.uz

Submission #681397

# Submission time Handle Problem Language Result Execution time Memory
681397 2023-01-13T02:14:19 Z vjudge1 Sure Bet (CEOI17_sure) C++14
0 / 100
 1 ms 468 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;
}

double 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(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(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;
}

Compilation message

sure.cpp: In function 'double calc(int, int)':
sure.cpp:38:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<double, std::vector<double>, std::greater<double> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if(q.size() > x)
      |            ~~~~~~~~~^~~
sure.cpp:49:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<double, std::vector<double>, std::greater<double> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if(q.size() > y)
      |            ~~~~~~~~~^~~
sure.cpp:61:1: warning: no return statement in function returning non-void [-Wreturn-type]
   61 | }
      | ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -