Submission #705444

#	Time	Username	Problem	Language	Result	Execution time	Memory
705444		penguin133	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	2516 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int besthub(int R, int L, int X[], long long B)
{
	long long P[R+5];
	P[0] = X[0];
	for(int i = 1; i < R; i++)P[i] = X[i] + P[i - 1];
  int ans = 0;
  for(int i = 0; i < R; i++){
	int lo = i, hi = R - 1, tmp = lo;
	while(lo <= hi){
		int mid = (lo + hi) >> 1;
		long long med = X[(i + mid) >> 1];
		if(P[mid] - P[(i + mid) >> 1] - med * (mid - ((i + mid) >> 1)) + med * (((i + mid) >> 1) - i + 1) - (P[(i + mid) >> 1] - (i > 0 ? P[i-1] : 0)) <= B)tmp = mid, lo = mid + 1;
		else hi = mid - 1;
	}
	ans = max(ans, tmp - i + 1);
  }
  return ans;
}

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