Submission #570737

#	Time	Username	Problem	Language	Result	Execution time	Memory
570737		vbee	Sure Bet (CEOI17_sure)	C++14	100 / 100	202 ms	7124 KiB

sure

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define fi first
#define se second
#define TASK "surebet"
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x >> (i)) & 1)

using namespace std;

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 1e5 + 7;

int n;
long double a[N], b[N], res, pre[N], pre2[N];
void trau(int i, vector<int> state){
    if (i == n){
        long double l = 0, r = 0, penalty = 0;
        for (int i = 0; i < state.size(); i++) {
            if (state[i] == 3) penalty -= 2;
            else if (state[i] != 4) penalty--;
        }
        for (int i = 0; i < state.size(); i++) if (state[i] != 4) {
            if (state[i] != 2){
                l += a[i + 1];
            }
            if (state[i] != 1){
                r += b[i + 1];
            }
        }
        res = max(res, min(l, r) + penalty);
        return ;
    }
    for (int j = 1; j <= 4; j++){
        vector<int> newstate = state;
        newstate.pb(j);
        trau(i + 1, newstate);
    }
}
int bs(long double cursum){
    int l = 1, r = n, ret = -1;
    while (l <= r){
        int middle = (r + l) / 2;
        if (pre2[middle] >= cursum) {
            ret = middle;
            r = middle - 1;
        }
        else l = middle + 1;
    }
    return ret;
}
int bs2(long double cursum){
    int l = 1, r = n, ret = -1;
    while (l <= r){
        int middle =  (r + l) / 2;
        if (pre[middle] >= cursum) {
            ret = middle;
            r = middle - 1;
        }
        else l = middle + 1;
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);
    // Nhớ tắt file
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    if (n <= 10){
        vector<int> temp;
        trau(0, temp);
        cout << fixed << setprecision(4) << res;
    }
    else if (n <= 1000){
        sort(a + 1, a + 1 + n, greater<long double>());
        sort(b + 1, b + 1 + n, greater<long double>());
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
        for (int i = 1; i <= n; i++) pre2[i] = pre2[i - 1] + b[i];
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= n; j++){
                res = max(res, min(pre[i], pre2[j]) - i - j);
            }
        }
        cout << fixed << setprecision(4) << res;
    }
    else {
        sort(a + 1, a + 1 + n, greater<long double>());
        sort(b + 1, b + 1 + n, greater<long double>());
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
        for (int i = 1; i <= n; i++) pre2[i] = pre2[i - 1] + b[i];
        for (int i = 1; i <= n; i++){
            long double cursum = pre[i];
            int numget = bs(cursum);
            if (numget != -1){
                res = max(res, cursum - i - numget);
            }
        }
        for (int i = 1; i <= n; i++){
            long double cursum = pre2[i];
            int numget = bs2(cursum);
            if (numget != -1){
                res = max(res, cursum - i - numget);
            }
        }
        cout << fixed << setprecision(4) << res;
    }
    return 0;
}

Compilation message (stderr)

sure.cpp: In function 'void trau(int, std::vector<int>)':
sure.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0; i < state.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
sure.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i = 0; i < state.size(); i++) if (state[i] != 4) {
      |                         ~~^~~~~~~~~~~~~~

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