Submission #1003268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003268		vjudge1	Rice Hub (IOI11_ricehub)	C++17	42 / 100	1094 ms	3540 KiB

ricehub

#include<bits/stdc++.h>
#include "ricehub.h"
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
    ll n = R, i, j, ans = 0;
    ll h[n+5], pref[n+5];
    ll l = 1, r = L;
    vl v;
    v.pb(LLONG_MIN);
    pref[0] = 0;
    for(i = 1; i <= n; i++)
    {
        h[i] = X[i-1];
        pref[i] = pref[i-1] + h[i];
        v.pb(X[i-1]);
    }
    L = min(L, (int)h[n]);
    for(ll mid = 0; mid <= L; mid++)
    {
        ll lb = lower_bound(all(v), mid) - v.begin();
        ll tl = lb - 1, tr = lb + 1, sum1 = 0, sum2 = 0;
        if(h[lb] != mid)
            tr = lb;
        //cout << "mid: " << mid << " lb: " << lb << "\n";
        while((tl >= 1 && tl <= n) || (tr >= 1 && tr <= n))
        {
            ll cost1 = LLONG_MAX, cost2 = LLONG_MAX;
            if(tl >= 1 && tl <= n)
                cost1 = mid - h[tl];
            if(tr >= 1 && tr <= n)
                cost2 = h[tr] - mid;
            //cout << "cost1: " << cost1 << " cost2: " << cost2 << "\n";
            if(cost1 == LLONG_MAX && cost2 == LLONG_MAX)
                break;
            if(cost1 <= cost2){
                sum1 += cost1;
                tl--;
            }
            else{
                sum2 += cost2;
                tr++;
            }
            if(sum1 + sum2 > B)
            {
                if(cost1 <= cost2){
                    sum1 -= cost1;
                    tl++;
                }
                else{
                    sum2 -= cost2;
                    tr--;
                }
                break;
            }
        }
        //cout << "sum1: " << sum1 << " sum2: " << sum2 << "\n";
        tl++, tr--;
        //cout << "tl: " << tl << " tr: " << tr << "\n";
        ans = max(ans, (tr - tl + 1));
    }
    return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:18:18: warning: unused variable 'j' [-Wunused-variable]
   18 |     ll n = R, i, j, ans = 0;
      |                  ^
ricehub.cpp:20:8: warning: unused variable 'l' [-Wunused-variable]
   20 |     ll l = 1, r = L;
      |        ^
ricehub.cpp:20:15: warning: unused variable 'r' [-Wunused-variable]
   20 |     ll l = 1, r = L;
      |               ^

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