oj.uz

Submission #307991

# Submission time Handle Problem Language Result Execution time Memory
307991 2020-09-29T17:23:45 Z tengiz05 Rice Hub (IOI11_ricehub) C++17
0 / 100
 4 ms 512 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], n;
long long b;
bool check(int cnt){
	//two pointers?
	int l=0, r=cnt-1;
	long long suml = 0, sumr = 0;
	long long m = a[cnt/2];
	for(int i=0; i<cnt/2; i++)suml += m-a[i];
	for(int i=cnt/2;i<cnt;i++)sumr += a[i]-m;
	
	bool flag = false;
	while(true){
	//	cout << suml << ' ' << sumr << '\n';
		if(b >= suml + sumr)flag = true;
		
		l++, r++;
		int median = l + cnt/2;
		if(r >= n)break;
		suml -= a[median-1]-a[l-1];
		suml += (cnt/2)*(a[median]-a[median-1]);
		sumr -= (cnt/2)*(a[median]-a[median-1]);
		sumr += a[r]-a[median];
	}
	return flag;
}
int besthub(int R, int L, int X[], long long B){
	n = R;
	b = B;
	for(int i=0;i<n;i++)a[i] = X[i];
	int l=0, r=R+1;
//	cout << check(3) << '\n';
	while(l+1<r){
		int mid = (l+r)/2;
		if(check(mid)){
			l = mid;
		}else {
			r = mid;
		}
	}
	return l;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -