This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "ricehub.h"
#include <bits/stdc++.h>
#define SIZE 100001
using namespace std;
int besthub(int r, int l, int x[], long long b)
{
long long pre[r + 1];
pre[0] = 0;
for (int i = 1;i<=r;i++)pre[i] = pre[i - 1] + 1LL*x[i - 1];
int ret = 0;
long long le = 1,ri = r;
while (le <= ri) {
bool f = false;
int mid = (le + ri) / 2;
//cout<<le<<" "<<ri<<" "<<mid<<endl;
for (int i = 0;i<r;i++) {
if (i + mid > r)continue;
long long cost = 0;
long long st = i , en = i + mid - 1 , med = (st + en) / 2;
cost += (med - st) * x[med];
cost -= pre[med] - pre[st];
cost += pre[en + 1] - pre[med + 1];
cost -= (en - med) * x[med];
if (cost <= b) {
ret = max(ret,mid);
f = true;
}
}
//cout<<f<<endl;
if (f) le = mid + 1;
else ri = mid - 1;
}
return ret;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |