Submission #477019

#	Time	Username	Problem	Language	Result	Execution time	Memory
477019		Mher	Rice Hub (IOI11_ricehub)	C++14	100 / 100	24 ms	3336 KiB

ricehub

#include "ricehub.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <bitset>
 
using namespace std;
 
const int N = 200003;
 
long long r, l, b;
long long x[N], p[N];
 
long long sum(int xl, int xr)
{
    return max(0ll, p[xr] - p[xl - 1]);
}
 
long long cost(int xl, int xr)
{
    int xm = (xl + xr) / 2;
    return sum(xm + 1, xr) - sum(xl, xm - ((xr - xl) % 2 == 0));
}
 
long long search(int ind)
{
    int xl = ind, xr = r;
    while (xl < xr)
    {
        int xm = (xl + xr + 1) / 2;
        if (cost(ind, xm) <= b)
        {
            xl = xm;
        }
        else
        {
            xr = xm - 1;
        }
    }
    return xl - ind + 1;
}
 
int besthub(int R, int L, int X[], long long B) {
	r = R;
  	l = L;
  	b = B;
    for (int i = 1; i <= r; i++)
    {
        x[i] = X[i - 1];
    }
    for (int i = 1; i <= r; i++)
    {
        p[i] = x[i] + p[i - 1];
    }
    long long ans = 0;
    for (int i = 1; i <= r; i++)
    {
        ans = max(ans, search(i));
    }
    return ans;
}

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