Submission #961050

#	Time	Username	Problem	Language	Result	Execution time	Memory
961050		raul2008487	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	5268 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
#define ll long long
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
    ll lo = 1, hi = R, mid, best = 1, sum, i, j, n = R, left, right, x;
    vl pr(n), sf(n);
    pr[0] = X[0];
    sf[n - 1] = X[n - 1];
    for(i = 1; i  < n; i++){
        pr[i] = pr[i - 1] + X[i];
    }
    for(i = n - 2; i >= 0; i--){
        sf[i] = sf[i + 1] + X[i];
    }
    lo = 1, hi = R;
    while(lo <= hi){
        mid = (lo + hi) >> 1;
        if(mid == 1){break;}
        bool ok = 0;
        for(i = 0; i < n - mid + 1; i++){
            if(mid & 1){
                left = right = i + (mid / 2);
                x = X[left];
            }
            else{
                left = i + (mid / 2)  - 1;
                right = left + 1;
                x = (X[right] + X[left]) / 2;
            }
            sum = ((left - i + 1) * x) - pr[left];
            if(i){sum += pr[i - 1];}
            sum += pr[i + mid - 1] - pr[right - 1] - (((i + mid - 1) - right + 1) * x);
            ok |= (sum <= B);
        }
        if(ok){
            best = mid;
            lo = mid + 1;
        }
        else{
            hi = mid - 1;
        }
    }
    return best;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:17:47: warning: unused variable 'j' [-Wunused-variable]
   17 |     ll lo = 1, hi = R, mid, best = 1, sum, i, j, n = R, left, right, x;
      |                                               ^

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