oj.uz

Submission #63000

# Submission time Handle Problem Language Result Execution time Memory
63000 2018-07-31T08:13:39 Z zetapi Rice Hub (IOI11_ricehub) C++14
68 / 100
 1000 ms 1972 KB 
//#include "ricehub.h"

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

#define pb  push_back
#define mp  make_pair
#define ll	long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;

int N,arr[MAX];

int cal(int ind,ll left)
{
	int pre=ind-1,nxt=ind,res=0;
	while(left>=0 and (pre>=0 or nxt<N))
	{
		if(pre<0 or (nxt<N and arr[ind]-arr[pre]>arr[nxt]-arr[ind]))
		{
			if(arr[nxt]-arr[ind]>left)
				break;
			left-=arr[nxt]-arr[ind];
			res++;
			nxt++;
		}
		else
		{
			if(arr[ind]-arr[pre]>left)
				break;
			left-=arr[ind]-arr[pre];
			res++;
			pre--;
		}	
	}
	return res;
}

ll sum[MAX];

ll cal(int L,int R)
{
	ll mid=(L+R)/2,bt=mid-L+1,at=R-mid+1;
	return arr[mid]*bt-(sum[mid]-sum[L-1])+(sum[R]-sum[mid-1])-arr[mid]*at;
}

int besthub(int R, int L, int X[], long long B)
{
	int res=0;
	N=R;
	for(int A=0;A<N;A++)
		arr[A+1]=X[A];
	for(int A=1;A<=N;A++)
	{
		sum[A]=sum[A-1]+arr[A];
		for(int C=1;C<=A;C++)
		{
			if(cal(C,A)<=B)
				res=max(res,A-C+1);
		}
	}
	//cout<<cal(3,5)<<"\n";
	return res;
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	int X[]={1,2,10,12,14};
	cout<<besthub(5,20,X,6);	
	return 0;
}*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 2 ms 560 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 6 ms 852 KB Output is correct
8 Correct 6 ms 880 KB Output is correct
9 Correct 4 ms 880 KB Output is correct
10 Correct 3 ms 880 KB Output is correct
11 Correct 6 ms 880 KB Output is correct
12 Correct 5 ms 940 KB Output is correct
13 Correct 8 ms 940 KB Output is correct
14 Correct 8 ms 940 KB Output is correct
15 Correct 3 ms 940 KB Output is correct
16 Correct 3 ms 940 KB Output is correct
17 Correct 6 ms 940 KB Output is correct
18 Correct 4 ms 940 KB Output is correct
19 Correct 6 ms 940 KB Output is correct
20 Correct 9 ms 940 KB Output is correct
21 Correct 68 ms 1024 KB Output is correct
22 Correct 65 ms 1024 KB Output is correct
23 Correct 68 ms 1024 KB Output is correct
24 Correct 80 ms 1112 KB Output is correct
25 Correct 70 ms 1112 KB Output is correct
26 Correct 78 ms 1112 KB Output is correct
27 Correct 61 ms 1112 KB Output is correct
28 Correct 79 ms 1128 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 1712 KB Output is correct
2 Execution timed out 1074 ms 1972 KB Time limit exceeded
3 Halted 0 ms 0 KB -