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 (sum > B)
{
if (q < p) q = p;
long long desq = abs(X[i] - X[p]); long long ddir = abs(X[q] - X[i]);
if (desq >= ddir) {sum -= desq; p++;}
else {sum -= ddir; q--;}
}
while (p-1 >= 0 && q+1 < R)
{
long long desq = (p > 0) ? abs(X[i] - X[p-1]) : (long long)(1e18 + 10);
long long ddir = (q < R-1) ? abs(X[q+1] - X[i]) : (long long)(1e18 + 10);
if (desq < ddir)
{
if (sum + desq > B) break;
sum += desq;
p--;
}
else
{
if (sum + ddir > B) break;
sum += ddir;
q++;
}
}
while (p-1 >= 0)
{
long long desq = (p > 0) ? abs(X[i] - X[p-1]) : (long long)(1e18 + 10);
if (sum + desq > B) break;
sum += desq;
p--;
}
while (q+1 < R)
{
long long ddir = (q < R-1) ? abs(X[q+1] - X[i]) : (long long)(1e18 + 10);
if (sum + ddir > B) break;
sum += ddir;
q++;
}
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... |