Submission #1140748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140748		Sang	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	2376 KiB

ricehub

#include<bits/stdc++.h>
#include "ricehub.h"
using namespace std;

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int R, L, B, pref[N], a[N];

int get(int l, int r){
    int m = (l + r)/2;
    return (m - l + 1) * a[m] - (pref[m] - pref[l-1]) + pref[r] - pref[m] - (r - m) * a[m];
}

int32_t besthub(int32_t R, int32_t L, int32_t X[], long long B)
{
    FOR (i, 1, R) a[i] = X[i-1], pref[i] = pref[i-1] + a[i];
    int ans = 0;
    int j = 1;
    FOR (i, 1, R){
        while (get(j, i) > B) ++j;
        ans = max(ans, i - j + 1);
    }
    return ans;
}


//signed main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    if (fopen(task".inp", "r")){
//        freopen(task".inp", "r", stdin);
//        freopen(task".out", "w", stdout);
//    }
//    cin >> R >> L >> B;
//    FOR (i, 1, R) cin >> a[i], pref[i] = pref[i-1] + a[i];
//    int ans = 0;
//    int j = 1;
//    FOR (i, 1, R){
//        while (get(j, i) > B) ++j;
//        ans = max(ans, i - j + 1);
//    }
//    cout << ans;
//
//    return 0;
//}

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