#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using i64 = long long;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;
constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();
#define RANGE(x) begin(x), end(x)
template <typename... T>
void DBG(T&&... args) {
((cerr << args << ' '), ...) << '\n';
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
out << '{';
for (size_t i = 0; i < vec.size()-1; ++i)
out << vec[i] << ", ";
out << vec.back() << '}';
return out;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
out << '(' << pr.first << ", " << pr.second << ')';
return out;
}
int besthub(int R, int L, int XCa[], long long B) {
vi X(XCa, XCa + R);
vi hub_count(L+2);
for (auto Xi : X) {
++hub_count[Xi];
}
vi lreward(L+2);
vl lcost(L+2);
for (int i = 1; i <= L; ++i) {
lreward[i] = lreward[i-1] + hub_count[i];
lcost[i] = lcost[i-1] + lreward[i-1];
}
vi rreward(L+2);
vl rcost(L+2);
for (int i = L; i >= 1; --i) {
rreward[i] = rreward[i+1] + hub_count[i];
rcost[i] = rcost[i+1] + rreward[i+1];
}
DBG(X);
DBG(hub_count);
DBG("left:");
DBG(lreward);
DBG(lcost);
DBG("right:");
DBG(rreward);
DBG(rcost);
auto lquery = [&] (int Xm, int Xl) {
i64 dist = Xm-Xl;
i64 maxcost = lcost[Xm] - lcost[Xl] - dist*lreward[Xl-1];
i64 mincost = hub_count[Xl]? (maxcost-(hub_count[Xl]-1)*dist): maxcost;
return tuple{lreward[Xm]-lreward[Xl-1], mincost, maxcost};
};
auto rquery = [&] (int Xm, int Xr) {
i64 dist = Xr-Xm;
i64 maxcost = rcost[Xm] - rcost[Xr] - dist * rreward[Xr+1];
i64 mincost = hub_count[Xr]? (maxcost-(hub_count[Xr]-1)*dist): maxcost;
return tuple{rreward[Xm]-rreward[Xr+1], mincost, maxcost};
};
auto range_query = [&] (int Xm, int Xl, int Xr) {
auto [lr, lcmin, lcmax] = lquery(Xm, Xl);
auto [rr, rcmin, rcmax] = rquery(Xm, Xr);
i64 total_cost = lcmax + rcmax;
if (Xl == 1 && Xr == 4 && Xm == 3) {
DBG(lcmin, lcmax, rcmin, rcmax);
DBG(total_cost);
DBG(B);
DBG("12312312321321321312321");
}
if (total_cost <= B) {
return pair{lr+rr-hub_count[Xm], total_cost};
} else if (lcmin + rcmin <= B) {
int ldist = Xm-Xl;
int rdist = Xr-Xm;
i64 overcost = total_cost - B;
int reward = lr+rr-hub_count[Xm];
DBG("overcost", overcost);
if (ldist < rdist) {
DBG("RIGHT FIRST");
if (rdist == 0) while (1) new i64[100000000];
int to_remove = (overcost+rdist-1) / rdist;
if (hub_count[Xr] - to_remove < 1) {
to_remove = hub_count[Xr]-1;
}
overcost -= to_remove * rdist;
reward -= to_remove;
if (overcost > 0) {
if (ldist == 0) while (1) new i64[100000000];
to_remove = (overcost+ldist-1)/ldist;
if (hub_count[Xl] - to_remove < 1) while (1) new i64[100000000];
overcost -= to_remove * ldist;
reward -= to_remove;
}
} else {
DBG("LEFT FIRST");
if (ldist == 0) while (1) new i64[100000000];
int to_remove = (overcost+ldist-1) / ldist;
if (hub_count[Xl] - to_remove < 1) {
to_remove = hub_count[Xl]-1;
}
DBG(to_remove);
overcost -= to_remove * ldist;
reward -= to_remove;
DBG("overcost 2:", overcost);
if (overcost > 0) {
if (rdist == 0) while (1) new i64[100000000];
to_remove = (overcost+rdist-1)/rdist;
if (hub_count[Xr] - to_remove < 1) while (1) new i64[100000000];
overcost -= to_remove * rdist;
reward -= to_remove;
}
}
if (overcost > 0) while (1) new i64[100000000]; // cant happen :)
if (Xl == 1 && Xr == 4 && Xm == 3) {
DBG("overcost result:", reward, B + overcost);
}
return pair{reward, B + overcost};
} else {
return pair{int(), B+1};
}
};
vi Xunique = X;
Xunique.erase( unique( Xunique.begin(), Xunique.end() ), Xunique.end() );
int xbeg = X.front();
int xend = X.back();
int ans = 0;
for (int xl = xbeg; xl <= xend; ++xl) if (hub_count[xl]) {
for (int xr = xl; xr <= xend; ++xr) if (hub_count[xr]) {
for (int x = xl; x <= xr; ++x) {
auto [reward, cost] = range_query(x, xl, xr);
if (cost <= B) {
if (reward > ans) {
DBG("pos:", x, xl, xr);
DBG("rice+cost:", reward, cost);
ans = reward;
}
}
}
}
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
320 KB |
Output is correct |
| 4 |
Correct |
3 ms |
212 KB |
Output is correct |
| 5 |
Correct |
3 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
6 ms |
212 KB |
Output is correct |
| 4 |
Correct |
6 ms |
336 KB |
Output is correct |
| 5 |
Correct |
16 ms |
360 KB |
Output is correct |
| 6 |
Correct |
15 ms |
340 KB |
Output is correct |
| 7 |
Correct |
20 ms |
340 KB |
Output is correct |
| 8 |
Correct |
20 ms |
368 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
3 ms |
212 KB |
Output is correct |
| 12 |
Correct |
3 ms |
212 KB |
Output is correct |
| 13 |
Correct |
6 ms |
212 KB |
Output is correct |
| 14 |
Correct |
5 ms |
316 KB |
Output is correct |
| 15 |
Correct |
59 ms |
420 KB |
Output is correct |
| 16 |
Correct |
63 ms |
376 KB |
Output is correct |
| 17 |
Correct |
7 ms |
320 KB |
Output is correct |
| 18 |
Correct |
5 ms |
212 KB |
Output is correct |
| 19 |
Correct |
36 ms |
396 KB |
Output is correct |
| 20 |
Correct |
37 ms |
384 KB |
Output is correct |
| 21 |
Correct |
52 ms |
440 KB |
Output is correct |
| 22 |
Correct |
52 ms |
380 KB |
Output is correct |
| 23 |
Execution timed out |
1084 ms |
728 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
388 ms |
720 KB |
Output is correct |
| 2 |
Correct |
391 ms |
808 KB |
Output is correct |
| 3 |
Execution timed out |
1083 ms |
27528 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1071 ms |
6984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
