Submission #871822

#	Time	Username	Problem	Language	Result	Execution time	Memory
871822		dsyz	Rice Hub (IOI11_ricehub)	C++17	100 / 100	24 ms	2676 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)

int besthub(int R, int L, int X[], long long B){
	if(R <= 5000){
		ll maximum = 0;
		for(ll pos = 0;pos < R;pos++){
			ll Lptr = pos;
			ll Rptr = pos;
			ll curcost = 0;
			while(Lptr > 0 && curcost + abs(X[pos] - X[Lptr - 1]) <= B){
				curcost += abs(X[pos] - X[Lptr - 1]);
				Lptr--;
			}
			while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
				curcost += abs(X[pos] - X[Rptr + 1]);
				Rptr++;
			}
			while(Rptr < R - 1 && abs(X[pos] - X[Lptr]) > abs(X[pos] - X[Rptr + 1])){
				curcost -= abs(X[pos] - X[Lptr]);
				curcost += abs(X[pos] - X[Rptr + 1]);
				Lptr++;
				Rptr++;
				while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
					curcost += abs(X[pos] - X[Rptr + 1]);
					Rptr++;
				}
			}
			maximum = max(maximum,Rptr - Lptr + 1);
		}
		return maximum;
	}else{
		ll maximum = 0;
		ll Lptr = 0;
		ll Rptr = 0;
		ll curcost = 0;
		while(Lptr > 0 && curcost + abs(X[0] - X[Lptr - 1]) <= B){
			curcost += abs(X[0] - X[Lptr - 1]);
			Lptr--;
		}
		while(Rptr < R - 1 && curcost + abs(X[0] - X[Rptr + 1]) <= B){
			curcost += abs(X[0] - X[Rptr + 1]);
			Rptr++;
		}
		maximum = max(maximum,Rptr - Lptr + 1);
		for(ll pos = 1;pos < R;pos++){
			if(Rptr >= pos){
				curcost += ((pos - Lptr) * abs(X[pos] - X[pos - 1]));
				curcost -= ((Rptr - pos + 1) * abs(X[pos] - X[pos - 1]));
			}else{
				curcost += ((pos - Lptr) * abs(X[pos] - X[pos - 1]));
				while(Rptr < pos){
					Rptr++;
					curcost += abs(X[pos] - X[Rptr]);
				}
			}
			while(Lptr < pos && curcost > B){
				curcost -= abs(X[pos] - X[Lptr]);
				Lptr++;
			}
			while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
				curcost += abs(X[pos] - X[Rptr + 1]);
				Rptr++;
			}
			while(Lptr + 1 <= pos && Rptr < R - 1 && abs(X[pos] - X[Lptr]) > abs(X[pos] - X[Rptr + 1])){
				curcost -= abs(X[pos] - X[Lptr]);
				curcost += abs(X[pos] - X[Rptr + 1]);
				Lptr++;
				Rptr++;
				while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
					curcost += abs(X[pos] - X[Rptr + 1]);
					Rptr++;
				}
			}
			maximum = max(maximum,Rptr - Lptr + 1);
		}
		return maximum;
	}
}

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