#include <bits/stdc++.h>
using namespace std;
int main()
{
int64_t m, l;
cin >> m >> l;
vector<int64_t> a(2 * m + 1);
for (int64_t &x : a)
cin >> x;
if (l < 0)
{
l = -l;
for (int64_t i = 0; i < m; i++)
swap(a[m - i - 1], a[m + i + 1]);
}
int64_t p = 0, total_added = 0;
vector<int64_t> b(a.begin(), a.end());
for (int64_t i = -m; i <= 0; i++)
p += a[i + m] * i, b[i + m] = 0;
for (int64_t i = 1; i <= m; i++)
{
for (int64_t j = 62; j >= 0; j--)
if (1LL << j <= b[i + m] && p + (1LL << j) * i <= l)
{
p += (1LL << j) * i;
b[i + m] -= 1LL << j;
total_added += 1LL << j;
}
}
if (p < l - m)
{
b = vector<int64_t>(a.begin(), a.end());
for (int64_t i = 0; i <= m; i++)
p += a[i + m] * i, b[i + m] = 0;
for (int64_t i = -1; i >= -m; i--)
{
for (int64_t j = 62; j >= 0; j--)
if (1LL << j <= b[i + m] && p + (1LL << j) * i >= l)
{
p += (1LL << j) * i;
b[i + m] -= 1LL << j;
total_added += 1LL << j;
}
}
if (p < l - m)
{
cout << "impossible\n";
return 0;
}
}
// l resides at m * m.
vector<int64_t> dp1(2 * m * m + 1, 0), dp2(2 * m * m + 1, 0);
dp1[m * m - (l - p)] = total_added;
for (int64_t i = -m; i <= m; i++)
{
for (int64_t j = 0; j < dp1.size(); j++)
{
int64_t max_add = min<int64_t>(b[i + m], m),
max_remove = min<int64_t>(a[i + m] - b[i + m], m);
for (int64_t k = 0;
1LL << k <= max_add &&
0 <= j + (1LL << k) * i && j + (1LL << k) * i < dp1.size();
k++)
if (dp1[j])
{
dp2[j + (1LL << k) * i] = max<int64_t>(dp2[j + (1LL << k) * i], dp1[j] + (1LL << k));
max_add -= 1LL << k;
}
if (0 <= j + max_add * i && j + max_add * i < dp1.size())
dp2[j + max_add * i] = max<int64_t>(dp2[j + max_add * i], dp1[j] + max_add);
for (int64_t k = 0;
1LL << k <= max_remove &&
0 <= j - (1LL << k) * i && j - (1LL << k) * i < dp1.size();
k++)
if (dp1[j])
{
dp2[j - (1LL << k) * i] = max<int64_t>(dp2[j - (1LL << k) * i], dp1[j] - (1LL << k));
max_remove -= 1LL << k;
}
if (0 <= j - max_remove * i && j - max_remove * i < dp1.size())
dp2[j - max_remove * i] = max<int64_t>(dp2[j - max_remove * i], dp1[j] - max_remove);
}
swap(dp1, dp2);
for (size_t i = 0; i < dp1.size(); i++)
dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]);
}
if (!dp1[m * m])
cout << "impossible\n";
else
cout << dp1[m * m] << '\n';
}
Compilation message
vault.cpp: In function 'int main()':
vault.cpp:64:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int64_t j = 0; j < dp1.size(); j++)
| ~~^~~~~~~~~~~~
vault.cpp:71:64: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | 0 <= j + (1LL << k) * i && j + (1LL << k) * i < dp1.size();
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:78:57: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (0 <= j + max_add * i && j + max_add * i < dp1.size())
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:83:64: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | 0 <= j - (1LL << k) * i && j - (1LL << k) * i < dp1.size();
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:90:63: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if (0 <= j - max_remove * i && j - max_remove * i < dp1.size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
