Submission #570777

#	Time	Username	Problem	Language	Result	Execution time	Memory
570777		bojackduy	Sure Bet (CEOI17_sure)	C++14	20 / 100	6 ms	212 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 = 1e5 + 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;
double a[N], b[N], res;
double ts(int i, double sum) {
    int l = 1, r = n, x = 0;
    while (l <= r) {
        int midl = (2 * l + r) / 3;
        int midr = (l + 2 * r) / 3;
        if (min(sum - midl - i, b[midl] - midl - i) > min(sum - midr - i, b[midr] - midr - i)) {
            r = midr - 1;
            x = midl;
        } else l = midl + 1;
    }
return min(sum - x - i, b[x] - x - i);
}
double ts1(int i, double sum) {
    int l = 1, r = n, x = 0;
    while (l <= r) {
        int midl = (2 * l + r) / 3;
        int midr = (l + 2 * r) / 3;
        if (min(sum - midl - i, a[midl] - midl - i) > min(sum - midr - i, a[midr] - midr - i)) {
            r = midr - 1;
            x = midl;
        } else l = midl + 1;
    }
return min(sum - x - i, a[x] - x - i);
}
void iuq(int i, int cnt, double sum, double sum2) {
    if (i == n) {
        maxi(res, min(sum, sum2) - cnt);
        return ;
    }
    iuq(i + 1, cnt, sum, sum2);
    iuq(i + 1, cnt + 1, sum + a[i + 1], sum2);
    iuq(i + 1, cnt + 1, sum, sum2 + b[i + 1]);
    iuq(i + 1, cnt + 2, sum + 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<double>());
        sort(allr(b, n), greater<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]));
        }
        for (int i = 1; i <= n; i++) {
            maxi(res, ts1(i, b[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