Submission #1041398

#TimeUsernameProblemLanguageResultExecution timeMemory
1041398That_SalamanderRice Hub (IOI11_ricehub)C++17
100 / 100
9 ms1884 KiB
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <set> #include <cstring> #include <queue> #include <unordered_set> #include <unordered_map> #define FOR(var,bound) for(int var = 0; var < bound; var++) #define FORB(var,lb,ub) for (int var = lb; var < ub; var++) #define FORR(var,bound) for(int var = bound-1; var >= 0; var--) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef pair<int, int> pii; int besthub(int R, int L, int X[], ll B) { ll currCost = 0; int lidx = 0; int ridx = -1; int best = 0; while (ridx < R - 1) { if (currCost + (X[ridx + 1] - X[0]) <= B) { currCost += X[++ridx] - X[0]; } else break; } best = (ridx - lidx + 1); //cout << "If hub is at " << X[0] << " can reach " << best << " farms!" << endl; FORB(i, 1, R) { int numMovingBack = (i - lidx); int numMovingForward = (ridx - i + 1); currCost += numMovingBack * (ll) (X[i] - X[i-1]); currCost -= numMovingForward * (ll) (X[i] - X[i-1]); if (ridx < i) { ridx = i; } while (currCost > B) { if (X[ridx] - X[i] < X[i] - X[lidx]) { currCost -= (X[i] - X[lidx++]); } else { currCost -= (X[ridx--] - X[i]); } } while (ridx < R - 1) { if (currCost + X[ridx + 1] - X[i] <= B) { currCost += X[++ridx] - X[i]; } else if (ridx > lidx && X[i] - X[lidx] > X[ridx+1] - X[i]) { currCost += X[++ridx] - X[i]; currCost -= X[i] - X[lidx++]; } else break; } if (ridx == R - 1) { while (lidx > 0 && currCost + X[i] - X[lidx-1] <= B) { currCost += X[i] - X[lidx-1]; lidx--; } } best = max(best, ridx - lidx + 1); //cout << "If hub is at " << X[i] << " can reach " << ridx - lidx + 1 << " farms!" << endl; //cout << "Cost = " << currCost << endl; /*int count = 1; ll cost = 0; int nl = i - 1; int nr = i + 1; while (nl >= 0 && nr < R) { if (X[nr] - X[i] > X[i] - X[nl]) { if (cost + X[i] - X[nl] > B) break; cost += X[i] - X[nl]; count++; nl--; } else { if (cost + X[nr] - X[i] > B) break; cost += X[nr] - X[i]; count++; nr++; } } if (nl < 0) { while (nr < R) { if (cost + X[nr] - X[i] > B) break; cost += X[nr] - X[i]; count++; nr++; } } else { while (nl >= 0) { if (cost + X[i] - X[nl] > B) break; cost += X[i] - X[nl]; count++; nl--; } } best = max(best, count);*/ } return best; } #ifdef LOCAL_TEST int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int R, L, B; cin >> R >> L >> B; vector<int> X(R); FOR(i, R) cin >> X[i]; cout << besthub(R, L, X.data(), B) << endl; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...