Submission #1027267

#TimeUsernameProblemLanguageResultExecution timeMemory
1027267vjudge1Sure Bet (CEOI17_sure)C++17
100 / 100
228 ms11972 KiB
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define el '\n'
#define pb push_back
#define mp make_pair
#define niggers                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define file(name)                    \
    freopen(name ".inp", "r", stdin); \
    freopen(name ".out", "w", stdout);

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

const ll MOD = 1e9 + 7;
const int inf = 1e9;
const int mxN = 1e2 + 5;
const int mxM = 1e3 + 5;
const int N = 2e5 + 5;

int hx[] = {-1, 0, 1, 0};
int hy[] = {0, 1, 0, -1};

long double a[N], b[N], psa[N], psb[N];
;
int main()
{
    // freopen("b.inp", "r", stdin);
    // freopen("b.out", "w", stdout);
    ll pinkkiu = 1;
    // cin >> pinkkiu;
    while (pinkkiu--)
    {
        ll n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i] >> b[i];
        }
        sort(a + 1, a + n + 1, greater<>());
        sort(b + 1, b + n + 1, greater<>());

        for (int i = 1; i <= n; ++i)
        {
            psa[i] = psa[i - 1] + a[i];
            psb[i] = psb[i - 1] + b[i];
        }
        // for(int i = 1;i <= n ; ++i){
        //     cout << psa[i] << ' ' << psb[i] << endl;
        // }
        long double ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            // cout << psa[i] << ' ' << psb[i] << endl;
            int l = 1, r = n;
            ll pos = -1;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (psb[mid] >= psa[i])
                {
                    r = mid - 1;
                    pos = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
            // cout << pos << ' ';

            if (pos != -1)
            {
                ans = max(ans, psa[i] - (1.0) * i - 1.0 * pos);
                // cerr << ans << ' ';
            }
        }
        for (int i = 1; i <= n; ++i)
        {
            int l = 1, r = n;
            ll pos = -1;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (psa[mid] >= psb[i])
                {
                    r = mid - 1;
                    pos = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
            if (pos != -1)
            {
                ans = max(ans, psb[i] - 1.0 * i - 1.0 * pos);
            }
        }
        cout << fixed << setprecision(4) << ans;
    }
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:68:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |                 int mid = l + r >> 1;
      |                           ~~^~~
sure.cpp:93:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |                 int mid = l + r >> 1;
      |                           ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...