Submission #770579

#	Time	Username	Problem	Language	Result	Execution time	Memory
770579		ByeWorld	Rice Hub (IOI11_ricehub)	C++14	100 / 100	13 ms	2940 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+100;
const ll INF = 2e18+10;

int n; ll b;
int a[MAXN]; ll pref[MAXN];

bool cost(int cnt){
	ll mn = INF;
	for(int l = 1; l+cnt-1 <= n; l++){
		int r = l + cnt-1; int mid = ((l+r+1)>>1);
		if((pref[r]-pref[mid-1]) - 1ll*(r-mid+1)*a[mid] + (1ll*(mid-l)*a[mid])-(pref[mid-1]-pref[l-1]) <= b) return 1;
	}
	return 0;
}

int besthub(int R, int L, int X[], long long B){
	n = R; b = B;
	for(int i=1; i<=n; i++){
		a[i] = X[i-1]; pref[i] = pref[i-1] + a[i];
	}

	int l = 1; int r = n; int mid = 0; int cnt = 0;
	while(l <= r){
		mid = ((l+r)>>1);
		if(cost(mid)){
			cnt = mid; l = mid+1;
		} else r = mid-1;
	}
	return cnt;
}

Compilation message (stderr)

ricehub.cpp: In function 'bool cost(int)':
ricehub.cpp:18:5: warning: unused variable 'mn' [-Wunused-variable]
   18 |  ll mn = INF;
      |     ^~

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