Submission #335867

#	Time	Username	Problem	Language	Result	Execution time	Memory
335867		sumit_kk10	Rice Hub (IOI11_ricehub)	C++14	0 / 100	6 ms	656 KiB

ricehub

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
 
long long int besthub(int n, int l, int a[], long long int b){
	long long int pre_sum[n] = {0}, suf_sum[n] = {0};
	pre_sum[0] = a[0];
	suf_sum[n - 1] = a[n - 1];
	for(int i = 1; i < n; ++i)
		pre_sum[i] = pre_sum[i - 1] + a[i];
	for(int i = n - 2; i >= 0; --i)
		suf_sum[i] = suf_sum[i + 1] + a[i];
	long long int ans = 1;
	for(int i = 0; i < n; ++i){
		int low = i + 1, high = n - 1, cur = i, cur1 = i;
		while(low <= high){
			int mid = (low + high) / 2;
			long long int x = pre_sum[mid] - pre_sum[i];
			x -= (a[i] * (mid - i));
			if(x > b)
				high = mid - 1;
			else{
				low = mid + 1;
				cur = mid;
			}
		}
		// cout << cur << ' ';
		if(i != 0){
			low = 0, high = i - 1;
			while(low <= high){
				int mid = (low + high) / 2;
				long long int x = suf_sum[mid] - suf_sum[i];
				x -= (a[i] * (i - mid));
				x = abs(x);
				if(x > b)
					low = mid + 1;
				else{
					cur1 = mid;
					high = mid - 1;
				}
			}
		}
		// cout << cur1 << '\n';
		ans = max(ans, (long long int) cur - cur1 + 1);
	}
	return ans;
}

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