# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
872468 | 2023-11-13T07:22:04 Z | StefanL2005 | Rice Hub (IOI11_ricehub) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "ricehub.h" using namespace std; #define ll long long int besthub(int R, int L, vector<int> X, ll B) { vector<ll> dp(R); for (int i = 1; i < R; i++) dp[0] += (X[i] - X[0]); ll sum = dp[0]; int right = R, left = 0; for (int i = 1; i < R; i++) { right--; left++; if (X[i] == X[i - 1]) { dp[i] = dp[i - 1]; continue; } int dif = X[i] - X[i - 1]; sum = sum - dif * right + dif * left; dp[i] = sum; } ll Min = dp[0]; int poz = 0; for (int i = 0; i < R; i++) if (dp[i] < Min) { Min = dp[i]; poz = i; } int c1 = poz - 1, c2 = poz + 1; ; bool done_change = true; int nr = 1; while (done_change) { done_change = false; cout<< "Budget: " << B << "\n"; if (c1 < 0 && c2 >= R) break; if (c1 >= 0 && (c2 >= R || X[poz] - X[c1] < X[c2] - X[poz])) { nr++; done_change = true; B -= (X[poz] - X[c1]); c1--; } else if (c2 < R && (c1 < 0 || X[c2] - X[poz] < X[poz] - X[c1])) { nr++; done_change = true; B -= (X[c2] - X[poz]); c2++; } if (B < 0) { nr--; done_change = false; } } return nr; }