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 <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
int findResp(int& R, int& L, int X[], long long& B, int i)
{
int p = i; int q = i+1;
long long sum = 0; int respi = 0;
while (p >= 0 && q < R)
{
long long desq = abs(X[i] - X[p]); long long ddir = abs(X[q] - X[i]);
if (desq < ddir)
{
if (sum + desq > B) break;
sum += desq;
p--;
respi++;
}
else
{
if (sum + ddir > B) break;
sum += ddir;
q++;
respi++;
}
}
while (p >= 0)
{
long long desq = abs(X[i] - X[p]);
if (sum + desq > B) break;
sum += desq;
p--;
respi++;
}
while (q < R)
{
long long ddir = abs(X[q] - X[i]);
if (sum + ddir > B) break;
sum += ddir;
q++;
respi++;
}
// cerr << i << " " << sum << " " << respi << '\n';
return respi;
}
int besthub(int R, int L, int X[], long long B)
{
int resp = 0;
int p = 0; int q = 0; long long sum = 0;
for (int i = 0; i < R; i++)
{
// cerr << p << " " << q << " " << sum << '\n';
while (p < R && q < R)
{
if (q < p) q = p;
long long desq = abs(X[i] - X[p]); long long ddir = abs(X[q+1] - X[i]);
// cerr << desq << " " << ddir << '\n';
if (sum > B) {sum -= desq; p++;}
else if (sum + ddir <= B) {sum += ddir; q++;}
else if (ddir <= desq) {sum += (ddir - desq); p++; q++;}
else break;
}
resp = max(resp, (q - p + 1));
if (p <= i && i+1 < R) sum += (long long)((min(i, q) - p + 1) * (abs(X[i+1] - X[i])));
if (q > i && i+1 < R) sum -= (long long)((q - max(i, p-1)) * (abs(X[i+1] - X[i])));
}
return resp;
}
# | 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... |