Submission #570766

#	Time	Username	Problem	Language	Result	Execution time	Memory
570766		bojackduy	Sure Bet (CEOI17_sure)	C++14	20 / 100	2086 ms	340 KiB

sure

#include<bits/stdc++.h>
#define task 
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define allr(x, sz) (x) + 1, (x) + 1 + sz
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MASK(x) (1LL<<(x))
#define BIT(x,i) (((x)>>(i))&1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

const int N = 1e6 + 1;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (x > y) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}
void file() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen(task.in, r, stdin);
    //freopen(task.out, w, stdout);
return ;
}


int n;
long double a[N], b[N], res;
long double ts(int i, long double sum1) {
    int l = 1, r = n, x = 0;
    while (l <= r) {
        int midl = (2 * l + r) / 3;
        int midr = (l + 2 * r) / 3;
        if (min(sum1 - midl - i, b[midl] - midl - i) >= min(sum1 - midr - i, b[midr] - midr - i)) {
            r = midr - 1;
            x = midl;
        } else {
            l = midl - 1;
            x = midr;
        }
    }
return min(sum1 - x - i, b[x] - x - i);
}
void iuq(int i, int cnt, long double sum1, long double sum2) {
    if (i == n) {
        maxi(res, min(sum1, sum2) - cnt);
        return ;
    }
    iuq(i + 1, cnt, sum1, sum2);
    iuq(i + 1, cnt + 1, sum1 + a[i + 1], sum2);
    iuq(i + 1, cnt + 1, sum1, sum2 + b[i + 1]);
    iuq(i + 1, cnt + 2, sum1 + a[i + 1], sum2 + b[i + 1]);
}
void solve(int test = -1) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    if (n <= 10) {
        iuq(0, 0, 0.0, 0.0);
        cout << setprecision(4) << fixed << res;
    } else {
        sort(allr(a, n), greater<long double>());
        sort(allr(b, n), greater<long double>());
        for (int i = 1; i <= n; i++) a[i] += a[i - 1];
        for (int i = 1; i <= n; i++) b[i] += b[i - 1];
        for (int i = 1; i <= n; i++) {
            maxi(res, ts(i, a[i]));
        }
        cout << setprecision(4) << fixed << res;
    }

}

int32_t main()  {
    file();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}

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