Submission #421101

#	Time	Username	Problem	Language	Result	Execution time	Memory
421101		OttoTheDino	Rice Hub (IOI11_ricehub)	C++17	100 / 100	17 ms	2120 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define rep(i,s,e)                          for (int i = s; i <= e; ++i)
typedef long long ll;
int besthub (int r, int l, int x[], ll b) {
    int ans = 1, right = 0, cur = 1;
    ll tot = 0;
    deque<int> dq;
    dq.push_back(x[0]);
    rep (i,1,r-1) {
        while (right<r-1) {
            ll newy = tot;
            dq.push_back(x[right+1]);
            int nmid = dq[((int)dq.size()-1)/2];
            newy += dq.back()-nmid; 
            if (newy<=b) {
                tot = newy;
                ans = max(ans, ++cur);
                right++;
            }
            else {
                dq.pop_back();
                break;
            }
        }
        tot -= dq[((int)dq.size()-1)/2]-dq.front();
        if ((int)dq.size()%2==0) tot -= dq[(int)dq.size()/2]-dq[((int)dq.size()-1)/2];
        dq.pop_front();
        cur--;
    }
    return ans;
}

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