Submission #229560

#	Time	Username	Problem	Language	Result	Execution time	Memory
229560		monus1042	Rice Hub (IOI11_ricehub)	C++17	17 / 100	25 ms	768 KiB

ricehub

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

int besthub(int R, int L, int X[], long long B)	{
	int ans=1;
	ll cost=0;

	int l=0,r=0;
	for (int i=1; i<R; i++){
		if (cost + (X[i] - X[0]) <= B){
			ans++;
			cost += X[i] - X[0];
			r++;
		}else break;
	}

	for (int i=1; i<R; i++){
		ll dist=X[i] - X[i-1];
		if (r<i){
			r=i;
		}else{
			cost -= dist * (r-(i-1));
		}
		cost += dist * (i-l);
		if (cost == B) {}
		else if (cost < B){
			while(1){
				if (r+1 < R && cost + (X[r+1] - X[i]) <= B){
					cost += X[r+1] - X[i];
					r++;
				}else break;
			}
		}else{ // cost > B
			while(1){
				if (cost <= B) break;
				cost -= X[i] - X[l];
				l++;
			}
			//try to expand
			while(1){
				if (r+1 < R && cost + (X[r+1] - X[i]) <= B){
					cost += X[r+1] - X[i];
					r++;
				}else break;
			}
		}
		ans=max(ans, r-l+1);
	}

	return ans;
}

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