Submission #539175

#	Time	Username	Problem	Language	Result	Execution time	Memory
539175		astoria	Rice Hub (IOI11_ricehub)	C++14	100 / 100	15 ms	2508 KiB

ricehub

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

int besthub(int R, int L, int X[], long long B)
{
  long long r,l,b;
	r=R; l=L; b=B;
	long long x[r];
	for(long long i=0; i<r; i++) x[i] = X[i];
	
	long long mx=0;
	long long td = 0;
	long long ll=0, rr=0;
	while(td<=b&&rr!=r-1){
		if(td + x[rr+1]-x[0] <= b){ rr++; td+=(x[rr]-x[0]);}
		else break;
		//cout<<"KK"<<endl;
	}
	mx = max(mx, rr-ll+1);
	//cout<<ll<<' '<<rr<<endl;
	for(long long i=1; i<r; i++){
		long long lef = i-ll, ri = rr-i+1;
		td += ((lef-ri)*(x[i]-x[i-1]));
		//cout<<td<<endl;
		while(td>b){
			td-=(x[i]-x[ll]); ll++; 
			assert(ll<=r-1);
			//cout<<"HEY"<<endl;
		}
		//if(i==2) cout<<td<<endl;
		while(td<=b&&rr!=r-1){
			if(td + x[rr+1]-x[i] <= b){ rr++; td+=(x[rr]-x[i]);}
			else break;
			//cout<<"YK"<<endl;
		}
		
		//MAGIC
		while(abs(x[ll]-x[i]) >= abs(x[rr+1]-x[i]) && rr!=r-1){
			td -= abs(x[ll]-x[i]); td+=abs(x[rr+1]-x[i]);
			ll++; rr++;
		}
		
		//MAGIC 2
		if(rr==r-1){
			while(td <= b && ll!=0){
				if(td + abs(x[ll-1]-x[i]) <= b){ ll--; td+=abs(x[ll]-x[i]);}
				else break;
			}
		}
		
		mx=max(mx, rr-ll+1);
		//cout<<ll<<' '<<rr<<endl;
	}
	return mx;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:7:15: warning: variable 'l' set but not used [-Wunused-but-set-variable]
    7 |   long long r,l,b;
      |               ^

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