Submission #239311

#	Time	Username	Problem	Language	Result	Execution time	Memory
239311		aggu_01000101	Sure Bet (CEOI17_sure)	C++14	100 / 100	206 ms	3704 KiB

sure

#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
bool cmp(pair<pair<double, double>, int> a, pair<pair<double, double>, int> b){
    if(a.first.first < b.first.first) return true;
    if(b.first.first < a.first.first) return false;
    if(a.first.second > b.first.second) return true;
    return false;
}
signed main(){
    int n;
    cin>>n;
    double a[2][n];
    for(int i = 0;i<n;i++) cin>>a[0][i]>>a[1][i];
    sort(a[0], a[0]+n);
    sort(a[1], a[1]+n);
    if(a[0][n-1]<=2 && a[1][n-1]<=2){
        cout<<"0\n";
        return 0;
    }
    int ind[] = {n-1, n-1};
    vector<pair<pair<double, double>, int>> pq;
    double ans = 0;
    int inv = 0;
    pq.push_back({{0, a[0][n-1]}, 0});
    pq.push_back({{0, a[1][n-1]}, 1});
    sort(pq.begin(), pq.end(), cmp);
    while(ind[pq[0].second] >= 0){
        pair<pair<double, double>, int> curr = pq[0];
        curr.first.first += a[curr.second][ind[curr.second]--];
        inv++;
        if(ind[curr.second]>=0) curr.first.second = a[curr.second][ind[curr.second]];
        else curr.first.second = -INF;
        pq[0] = curr;
        sort(pq.begin(), pq.end(), cmp);
        ans = max(ans, pq[0].first.first - inv);
    }
    printf("%.4lf",(double)ans);

}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40