Submission #1202250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202250		adiyer	Rice Hub (IOI11_ricehub)	C++20	100 / 100	335 ms	21108 KiB

ricehub

#pragma once
#pragma GCC optimize("g", on)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first 
#define S second 

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 3; 
const int MAX = 2e4 + 11;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, lmt, ans;
ll a[N], p[N];

pair < ll, ll > f(ll i, ll x){
    ll L, R, l, r;
    l = 0, r = i;
    while(r - l > 1){
        ll md = (l + r) / 2;
        if(a[md] >= a[i] - x) r = md;
        else l = md;
    } 
    L = r;
    l = i, r = n + 1;
    while(r - l > 1){
        ll md = (l + r) / 2;
        if(a[md] <= a[i] + x) l = md;
        else r = md;
    }
    R = l;
    return {(a[i] * (i - L + 1) - (p[i] - p[L - 1])) + ((p[R] - p[i]) - a[i] * (R - i)), R - L + 1};
}

int besthub(int R, int L, int X[], long long B){
    n = R, lmt = B;
    map < ll, ll > cnt;
    for(ll i = 1; i <= n; i++) a[i] = X[i - 1], p[i] = p[i - 1] + a[i], cnt[a[i]]++;
    for(ll i = 1; i <= n; i++){
        ll l = 0, r = L + 1;
        while(r - l > 1){
            ll md = (l + r) / 2;
            if(f(i, md).F <= lmt) l = md;
            else r = md;
        }
        ll c = cnt[a[i] - r] + cnt[a[i] + r];
        // cout << f(i, l).S << ' ' << (lmt - f(i, l).F) << '\n';
        ans = max(ans, f(i, l).S + min(c, (lmt - f(i, l).F) / r));
    }
    return ans;
}

Compilation message (stderr)

ricehub.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
ricehub.cpp:2:27: warning: '#pragma GCC optimize (string [,string]...)' does not have a final ')' [-Wpragmas]
    2 | #pragma GCC optimize("g", on)
      |                           ^~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32