#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
vi calcShifts(int a)
{
vi ans;
int i = 0;
while ((1 << i) <= a)
{
a -= (1 << i);
ans.push_back(i++);
}
while (i > 0)
if ((1 << --i) <= a)
ans.push_back(i), a -= (1 << i);
return ans;
}
int calcDP(vi &A, ll L, ll M)
{
int an = accumulate(A.begin(), A.begin() + M, 0);
int ap = accumulate(A.begin() + M + 1, A.begin() + 2 * M + 1, 0);
int MAXSIZE = 2 * M * max(an, ap) + 2;
vi dp(MAXSIZE, -1);
ll center = MAXSIZE / 2;
dp[center] = A[M];
for (int foo = 0; foo < 2; ++foo)
{
reverse(all(A)), reverse(all(dp));
for (ll m = 1; m <= M; ++m)
{
ll maxNum = A[m + M];
vi shifts = calcShifts(maxNum);
for (int i : shifts)
{
ll amount = (1 << i);
ll d = amount * m;
for (int j = sz(dp) - 1; j >= d; --j)
dp[j] = max(dp[j], (dp[j - d] != -1) ? dp[j - d] + amount : -1);
}
}
}
if (0 <= center + L && center + L < sz(dp))
return dp[center + L];
else
return -1;
}
pii calcPref(vi &A, int M, int L, ll &pref, ll &tmpans) // find first Prefix position { i, idx } with pref >= L, or { sz(A)-1 = 2 * M, A[2 * M] }
{
int i = 0;
tmpans = 0, pref = 0;
for (; i < M; ++i)
tmpans += A[i], pref += A[i] * (i - M);
if (pref >= L)
return {i, 0};
while (i < sz(A) && pref + A[i] * (i - M) < L)
{
pref += A[i] * (i - M);
tmpans += A[i];
++i;
}
if (i == sz(A))
return {i - 1, A[i - 1]};
ll delta = L - pref;
assert(delta >= 0); // The expectation after the while loop is, that one is able to forfill this shit with the A[i] * (i - M) stuff
int l = 0, r = A[i], m;
while (l < r)
{
m = (l + r) / 2;
ll v = (i - M) * m;
if (v < delta)
l = m + 1;
else
r = m;
}
pref += l * (i - M);
tmpans += l;
return {i, l};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll M, L;
cin >> M >> L;
vi A(2 * M + 1);
for (int i = 0; i < sz(A); ++i)
cin >> A[i];
cout << calcDP(A, L, M) << endl;
vi B(sz(A), 0);
ll dpMax = 0, dpMin = 0; // Obere Grenze und untere Grenze für das davon induzierte DP
for (int i = 0; i < sz(B); ++i)
{
if (i == M)
{
B[i] = A[i];
A[i] = 0;
continue;
}
B[i] = min(M - 1, A[i]);
A[i] -= B[i];
dpMax = max(dpMax, dpMax + B[i] * (i - M));
dpMin = min(dpMin, dpMin + B[i] * (i - M));
}
vi C;
for (ll b : B)
C.push_back(b);
ll li, lidx, ri, ridx, pref, tmpans;
tie(ri, ridx) = calcPref(A, M, L - dpMin + 1, pref, tmpans);
tie(li, lidx) = calcPref(A, M, L - dpMax, pref, tmpans);
for (int i = li; i < ri; ++i)
{
C[i] += A[i] - lidx;
lidx = 0;
}
C[ri] += ridx - lidx;
ll ans = -1;
ll tmp = calcDP(C, L - pref, M);
if (tmp != -1)
ans = tmpans + tmp;
if (ans == -1)
cout << "impossible\n";
else
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
