#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
using i64 = long long;
const int INF = 1000000007; //998244353;
int besthub(int R, int L, int X[], i64 B) {
ios::sync_with_stdio(0); cin.tie(0);
vector<pair<i64, i64>> at;
for (int i = 0; i < R; ++i) {
if (i == 0 || X[i] != X[i - 1]) at.push_back({X[i], 1LL});
else ++at.back().second;
}
int n = (int)at.size();
// for each city, find maximum number WITHIN BUDGET
// this can be done greedily
// if we add in the order of distance from current city
// we can binary search (yes!!!) for the size of the outer bound
// nlog^2n probably passes as well
vector<pair<i64, i64>> pref(n);
vector<i64> cd(n);
pref[0] = at[0];
cd[0] = at[0].first * at[0].second;
for (int i = 1; i < n; ++i) {
pref[i].first = pref[i - 1].first + at[i].first;
pref[i].second = pref[i - 1].second + at[i].second;
cd[i] = cd[i - 1] + at[i].first * at[i].second;
}
PAR2(at); PAR2(pref);
auto cost = [&] (i64 m, int i) -> i64 {
int lb = lower_bound(at.begin(), at.end(),
make_pair(at[i].first - m, 0LL)) - at.begin();
int rb = upper_bound(at.begin(), at.end(),
make_pair(at[i].first + m, 0LL)) - at.begin() - 1;
i64 ldist = cd[i] - cd[lb] + cd[lb];
i64 lcnt = pref[i].second - pref[lb].second + at[lb].second;
i64 rdist = cd[rb] - cd[i]+ cd[i];
i64 rcnt = pref[rb].second - pref[i].second + at[i].second;
//PV(lcnt); PV(ldist); PV(rcnt); PV(rdist);
return lcnt * at[i].first - ldist + rdist - rcnt * at[i].first;
};
auto abval = [&] (i64 x) -> i64 {
return max(x, -x);
};
int ans = 0;
for (int i = 0; i < n; ++i) {
i64 l = 0, r = L;
// make sure it COMPLETELY works
// then we can add on the edges if needed
while (r > l + 1) {
i64 m = (l + r) / 2;
//PV(m);
//PV(cost(m, i));
if (cost(m, i) <= B) {
l = m;
} else {
r = m - 1;
}
}
i64 res = (cost(r, i) <= B ? r : l), c = cost(res, i);
PV(res); PV(c);
int lb = lower_bound(at.begin(), at.end(),
make_pair(at[i].first - res, 0LL)) - at.begin();
int rb = upper_bound(at.begin(), at.end(),
make_pair(at[i].first + res, 0LL)) - at.begin() - 1;
int cnt = pref[rb].second - pref[lb].second + at[lb].second;
PV(cnt);
if (c < B) {
vector<pair<i64, i64>> extras;
PV(lb); PV(rb);
if (lb > 0) extras.push_back(at[lb - 1]);
if (rb < n - 1) extras.push_back(at[rb + 1]);
sort(extras.begin(), extras.end(), [&](pair<i64, i64> a, pair<i64, i64> b) {
return a.first - at[i].first < b.first - at[i].first;
});
for (int j = 0; j < (int) extras.size(); ++j) {
i64 rem = B - c, used = min(rem / abval(extras[j].first - at[i].first), extras[j].second);
cnt += used;
c += abval(extras[j].first - at[i].first) * used;
}
PAR2(extras); PV(cnt); PV(c);
}
ans = max(ans, cnt);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 8 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
1332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
