Submission #953898

#	Time	Username	Problem	Language	Result	Execution time	Memory
953898		4QT0R	Rice Hub (IOI11_ricehub)	C++17	49 / 100	11 ms	3932 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll besthub(int n, int L, int pos[], ll bud){
	ll l,p,sm;
	l=p=sm=0;
	while(p<n-1 && sm+pos[p+1]-pos[0]<=bud){
		p++;
		sm+=pos[p]-pos[0];
	}
	ll mx=p+1;
	for (ll i = 1; i<n; i++){
		sm+=(pos[i]-pos[i-1])*(i-l);
		sm-=(pos[i]-pos[i-1])*(p-i+1);
		while(sm>bud && l<i){
			sm-=pos[i]-pos[l];
			l++;
		}
		while(p<n-1 && sm+pos[p+1]-pos[i]<=bud){
			p++;
			sm+=pos[p]-pos[i];
		}
		while(l<i && p<n-1 && (pos[p+1]-pos[i])<(pos[i]-pos[l])){
			sm-=pos[i]-pos[l];
			l++;
			while(p<n-1 && sm+pos[p+1]-pos[i]<=bud){
				p++;
				sm+=pos[p]-pos[i];
			}
		}
		mx=max(mx,p-l+1);
	}
	return mx;
}

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