Submission #895868

#	Time	Username	Problem	Language	Result	Execution time	Memory
895868		starchan	Rice Hub (IOI11_ricehub)	C++17	100 / 100	18 ms	6780 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
ll a[MX];
ll pref[MX];
ll cost(int l, int r)
{
	if((r-l)%2)
	{
		int cnt = r-l+1;
		cnt/=2;
		int m = r-cnt;
		return pref[r]-2*pref[m]+pref[l-1];
	}
	else
	{
		int m = (l+r)/2;
		return pref[r]-pref[m-1]-pref[m]+pref[l-1];
	}
}
int besthub(int R, int L, int X[], ll B)
{
	pref[0] = 0;
	for(int i = 0; i < R; i++)
	{
		a[i+1] = (ll)X[i];
		pref[i+1] = a[i+1]+pref[i];
	}
	int ans = 0;
	for(int i = 1; i <= R; i++)
	{
		int l = i;
		int r = R+1;
		while(l < r)
		{
			int m = (l+r)/2;
			if(cost(i, m) > B)
				r = m;
			else
				l = m+1; 
		}
		l--;
		ans = max(ans, l-i+1);
	}
	return ans;
}

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