oj.uz

Submission #283263

# Submission time Handle Problem Language Result Execution time Memory
283263 2020-08-25T12:56:14 Z peijar Rice Hub (IOI11_ricehub) C++17
0 / 100
 4 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXN = 1e5+1;

ll prefixSum[MAXN];
int cntFields, maxCor, budget;
int cor[MAXN];

ll getCost(int l, int r)
{
	int mid = (l+r)/2-1;
	ll cost = (mid-l) * cor[mid] - (r-mid) * cor[mid] + prefixSum[r] + prefixSum[l-1] - 2*prefixSum[mid];
	return cost;
}

bool can(int want)
{
	for (int i(0); i + want <= cntFields; ++i)
		if (getCost(i+1, i+want) <= budget)
			return true;
	return false;
}

int besthub(int c, int m, int co[], ll b)
{
	budget = b;
	cntFields = c;
	maxCor = m;
	for (int i(0); i < cntFields; ++i)
		cor[i] = co[i];
	for (int i(0); i < cntFields; ++i)
		prefixSum[i+1] = prefixSum[i] + cor[i];

	int lo(0), up(cntFields);
	while (lo < up)
	{
		int mid = (lo+up+1)/2;
		if (can(mid)) lo = mid;
		else up = mid-1;
	}
	return lo;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 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 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

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