Submission #781475

#TimeUsernameProblemLanguageResultExecution timeMemory
781475asdfgraceRice Hub (IOI11_ricehub)C++17
0 / 100
44 ms1332 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...