oj.uz

Submission #346311

# Submission time Handle Problem Language Result Execution time Memory
346311 2021-01-09T09:59:53 Z Mefarnis Rice Hub (IOI11_ricehub) C++14
0 / 100
 3 ms 620 KB 
#include <algorithm>
#include "ricehub.h"
using namespace std;

long long getCost(int l , int r , int x[], long long sum[]) {
	int m = (l+r) >> 1;
	long long cost = 0;
	if(l < m)
		cost += (m-l) * (long long) x[m] - (sum[m-1] - sum[l-1]);
	if(m < r)
		cost += (sum[r] - sum[m]) - (r-m) * (long long) x[m];
	return cost;
}

int besthub(int n, int xmax, int x[], long long budget)
{
	int ans = 0;
	long long sum[n+1];
	sum[0] = 0;
	for( int i = 1 ; i <= n ; i++ )
		sum[i] = sum[i-1] + x[i-1];
	for( int l = 1 , r = 1 ; l <= n ; l++ ) {
		r = max(l,r);
		while(r < n && getCost(l,r+1,x,sum) <= budget)
			r++;
		ans = max(ans,r-l+1);
	}
	return ans;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

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