Submission #229485

#	Time	Username	Problem	Language	Result	Execution time	Memory
229485		kshitij_sodani	쌀 창고 (IOI11_ricehub)	C++17	100 / 100	30 ms	3072 KiB

ricehub

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
#include <ricehub.h>
llo it[100001];
llo pre[100001];
llo n;
llo bb;
llo check(llo st,llo en){
	llo mi=st+(en-st)/2;
	llo co=(mi-st+1)*it[mi];
	if(st==0){
		co-=pre[mi];
	}
	else{
		co-=(pre[mi]-pre[st-1]);
	}
	co-=(en-mi+1)*it[mi];
	if(mi==0){
		co+=pre[en];
	}
	else{
		co+=(pre[en]-pre[mi-1]);
	}
	return co<=bb;
}
int besthub(int nn,int coo,int tt[],llo b){
	n=(llo)nn;
	llo l,r;
	llo tot=0;
	llo ma=0;
	bb=b;
	
	for(llo i=0;i<n;i++){
		it[i]=(llo)tt[i];
	}
	pre[0]=it[0];
	for(llo i=1;i<n;i++){
		pre[i]=pre[i-1]+it[i];
	}
	for(llo i=0;i<n;i++){
		llo low=i;
		llo high=n-1;
		while(low<high-1){
			llo mid=(low+high)/2;
			if(check(i,mid)){
				low=mid;
			}
			else{
				high=mid-1;
			}
		}
		llo ans=low;
		if(check(i,high)){
			ans=high;
		}
		ma=max(ma,ans-i+1);
	}
	return ma;

/*	for(llo i=0;i<n;i++){
		if(i==0){
			l=0;
			r=-1;
			for(llo j=0;j<n;j++){
				if(tot+it[j]-it[0]<=b){
					tot+=(it[j]-it[0]);
					r+=1;
				}
				else{
					break;
				}
			}
			ma=max(ma,r-l+1);
		}
		else{
			tot+=abs(it[i]-it[i-1])*abs(l-i);
			tot-=abs(it[i]-it[i-1])*abs(r-i+1);
			llo llp=l;
			for(int j=llp;j<i;j++){
				if(tot>b){
					tot-=abs(it[j]-it[i]);
					l+=1;
				}
				else{
					break;
				}
			}
			int rr=r;
			for(llo j=rr+1;j<n;j++){
				if(abs(it[j]-it[i])<=abs(it[i]-it[l])){
					r+=1;
					tot+=abs(it[j]-it[i]);
					if(tot>b){
						l+=1;
						tot-=abs(it[i]-it[l-1]);
					}
				}
				else if(abs(it[j]-it[i])+tot<=b){
					r+=1;
					tot+=abs(it[j]-it[i]);
				}
				else{
					break;
				}
			}

			ma=max(ma,r-l+1);
		}

	}*/

	return ma;
}
/*int main(){
	llo cc[5];
	cc[0]=1;
	cc[1]=2;
	cc[2]=10;
	cc[3]=12;
	cc[4]=14;
	cout<<besthub(5,20,cc,(llo)6)<<endl;
	int r,l;
	llo b;
	cin>>r>>l>>b;
	int ac[r];
	for(int i=0;i<r;i++){
		cin>>ac[i];
	}
	cout<<besthub(r,l,ac,b)<<endl;
 
	return 0;
}*/

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, llo)':
ricehub.cpp:34:6: warning: unused variable 'l' [-Wunused-variable]
  llo l,r;
      ^
ricehub.cpp:34:8: warning: unused variable 'r' [-Wunused-variable]
  llo l,r;
        ^
ricehub.cpp:35:6: warning: unused variable 'tot' [-Wunused-variable]
  llo tot=0;
      ^~~

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