Submission #1300016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300016		zowi	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	2488 KiB

ricehub

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

long long pre[100005];

bool czy(vector<long long> &x,long long y,long long b)
{
	for(long long i = 1;i <= (long long)x.size()-y;++i)
	{
		long long mid = (i+i+y)/2;
		long long lewy = -pre[i-1]+pre[mid-1];
		long long prawy = -pre[mid]+pre[i+y-1];
		if(y%2 == 0) prawy += x[mid];
		//cout << lewy << ' ' << prawy << ' ' << i << ' ' << mid << endl;
		if(prawy-lewy <= b) return 1;
	}
	return 0;
}

int besthub(int r, int l, int x[], long long b)
{
	vector<long long> z = {0};
	for(long long i = 0;i < r;++i)
	{
		long long a = x[i];
		z.push_back(a);
		pre[i+1] = pre[i]+a;
	}
	long long l1 = 1,p = r,mid;
	while(l1 < p)
	{
		mid = (l1+p+1)/2;
		if(czy(z,mid,b))
		{
			l1 = mid;
		}
		else
		{
			p = mid-1;
		}
	}
	return l1;
}

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