Submission #898774

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
898774	2024-01-05T05:45:17 Z	Faisal_Saqib	Rice Hub (IOI11_ricehub)	C++17	100 / 100	139 ms	4896 KB

ricehub

#pragma once
#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector<long long> vp,pre={0};
long long b;
bool check(int r,int i,int mid,int take)
{
	if((r-i)>=(mid-take))
	{
		long long cur=0;
		long long sum_b=pre[i+1]-pre[i-take+1];
		cur+=((take*vp[i])-sum_b);
		long long sum_f=pre[i+mid-take+1]-pre[i+1];
		cur+=(sum_f-((mid-take)*vp[i]));
		if(cur<=b)
		{
			return 1;
		}
	}
	return 0;
}
int besthub(int r, int l, int x[], long long b1)
{
	b=b1;
	int ans=0;
	vp.push_back(-3e15);
	for(int i=0;i<r;i++)
		vp.push_back(x[i]);
	vp.push_back(3e15);
	for(auto i:vp)
		pre.push_back(pre.back()+i);
	for(int i=1;i<=r;i++)
	{
		// binary search on cnt
		int cnt_s=1;
		int cnt_e=r+1;
		// cout<<"index "<<i<<endl;
		while(cnt_s+1<cnt_e)
		{
			int mid=(cnt_s+cnt_e)/2;
			bool pos=0;
			// cout<<"For "<<mid<<' ';
			int take_s=0;
			int take_e=min(mid,i)+1;
			while(take_s+1<take_e)
			{
				int mid1=(take_s+take_e)/2;
				if((r-i)>=(mid-mid1))
				{
					long long sum_b=pre[i+1]-pre[i-mid1+1];
					sum_b=(mid1*vp[i])-sum_b;
					long long sum_f=(pre[i+mid-mid1+1])-(pre[i+1]);
					sum_f-=(mid-mid1)*vp[i];
					if(sum_b<=sum_f)
					{
						take_s=mid1;
					}
					else
					{
						take_e=mid1;
					}
				}
				else
				{
					// We have to take more from the element less than side so increase s to mid
					take_s=mid1;
				}
			}
			for(int error=-1;error<=1;error++)
			{
				if(check(r,i,mid,take_s+error))
				{
					pos=1;
					break;
				}
			}
			if(pos)
			{
				cnt_s=mid;	
			}
			else
			{
				cnt_e=mid;
			}
		}
		// int cnt=1;
		// long long tm=0;
		// int l=i-1;
		// int r=i+1;
		// while(min(vp[i]-vp[l],vp[r]-vp[i])<=(b-tm))
		// {
		// 	tm+=min(vp[i]-vp[l],vp[r]-vp[i]);
		// 	if((vp[i]-vp[l])==min(vp[i]-vp[l],vp[r]-vp[i]))
		// 	{
		// 		cnt++;
		// 		l--;
		// 	}
		// 	else
		// 	{
		// 		cnt++;
		// 		r++;
		// 	}
		// }
		ans=max(ans,cnt_s);
	}
	return ans;
}

Compilation message

ricehub.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	396 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	4 ms	604 KB	Output is correct
22	Correct	4 ms	604 KB	Output is correct
23	Correct	3 ms	604 KB	Output is correct
24	Correct	4 ms	600 KB	Output is correct
25	Correct	4 ms	604 KB	Output is correct
26	Correct	4 ms	604 KB	Output is correct
27	Correct	5 ms	604 KB	Output is correct
28	Correct	5 ms	604 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	984 KB	Output is correct
2	Correct	17 ms	984 KB	Output is correct
3	Correct	96 ms	4896 KB	Output is correct
4	Correct	139 ms	4816 KB	Output is correct
5	Correct	48 ms	3792 KB	Output is correct
6	Correct	55 ms	3792 KB	Output is correct
7	Correct	95 ms	4812 KB	Output is correct
8	Correct	132 ms	4812 KB	Output is correct
9	Correct	69 ms	3796 KB	Output is correct
10	Correct	66 ms	3796 KB	Output is correct
11	Correct	96 ms	4812 KB	Output is correct
12	Correct	136 ms	4816 KB	Output is correct
13	Correct	58 ms	3796 KB	Output is correct
14	Correct	53 ms	3796 KB	Output is correct
15	Correct	69 ms	4560 KB	Output is correct
16	Correct	97 ms	4560 KB	Output is correct
17	Correct	85 ms	4812 KB	Output is correct
18	Correct	120 ms	4812 KB	Output is correct
19	Correct	91 ms	4812 KB	Output is correct
20	Correct	127 ms	4812 KB	Output is correct