oj.uz

답안 #898774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898774 2024-01-05T05:45:17 Z Faisal_Saqib 쌀 창고 (IOI11_ricehub) C++17
100 / 100
 139 ms 4896 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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