| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 872472 | 2023-11-13T07:35:23 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
ll besthub(ll R, ll L, vector<ll> 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;
ll 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;
}