Submission #224548

#	Time	Username	Problem	Language	Result	Execution time	Memory
224548		T0p_	Rice Hub (IOI11_ricehub)	C++14	100 / 100	179 ms	3328 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;

long long pos[100100], qs[100100];

long long cost_r(int i, int j)
{
	if(i > j) return 0;
	return qs[j] - qs[i] - pos[i]*(j-i);
}

long long cost_l(int i, int j)
{
	return pos[j]*(j-i) - qs[j-1] + qs[i-1];
}

int solve_l(int i, long long bl)
{
	int l = 1, r = i;
	while(l != r)
	{
		int mid = (l+r)>>1;
		if(cost_l(mid, i) <= bl) r = mid;
		else l = mid+1;
	}
	return i-l;
}

int besthub(int R, int L, int X[], long long B)
{
	int ans = 1;

	for(int i=0 ; i<R ; i++)
	{
		pos[i+1] = X[i];
		qs[i+1] = qs[i] + X[i];
	}

	for(int i=1 ; i<=R ; i++)
	{
		int l=i, r = R;
		while(l != r)
		{
			int mid = (l+r+1)>>1;
			long long br = cost_r(i, mid);
			if(br > B)
			{
				r = mid-1;
				continue ;
			}
			long long bl = B - br;
			int hl = solve_l(i, bl);
			if(mid - i + hl >= mid - 1 - i + solve_l(i, B - cost_r(i, mid-1))) l = mid;
			else r = mid-1;
		}
		ans = max(ans, 1+l-i + solve_l(i, B - cost_r(i, l)));
	}
	return ans;
}

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