Submission #714044

#	Time	Username	Problem	Language	Result	Execution time	Memory
714044		Spade1	Rice Hub (IOI11_ricehub)	C++14	49 / 100	17 ms	2180 KiB

ricehub

#include <bits/stdc++.h>
#define ll long long
#include "ricehub.h"
//#include "grader.cpp"

using namespace std;

queue<int> qL, qR;

int besthub(int R, int L, int X[], ll B) {
    ll cost = 0, cur = 1;
    int ans = 0;
    for (int i = 0; i < R; ++i) {
        if (i != 0) cost += (X[i]-X[i-1])*qL.size();
        if (i != 0) cost -= (X[i]-X[i-1])*qR.size();
        if (!qR.empty() && qR.front() == X[i]) qR.pop();
        if (cur <= i) cur++;
        qL.push(X[i]);
        while (cost > B) {
            cost -= X[i]-qL.front();
            qL.pop();
        }
        while (cur < R) {
            if (cost + X[cur] - X[i] > B) {
                if (cost - (X[i]-qL.front()) + (X[cur]-X[i]) <= cost) {
                    cost -= X[i]-qL.front();
                    cost += X[cur]-X[i];
                    qL.pop();
                    qR.push(X[cur++]);
                }
                else break;
            }
            else {
                cost += X[cur] - X[i];
                qR.push(X[cur++]);
            }
        }
        int cur = qL.size() + qR.size();
        ans = max(ans, cur);
    }
    return ans;
}

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