#include <bits/stdc++.h>
using namespace std;
vector<long long> SolveDP(long long N, long long LIM, vector<long long> List, vector<long long> Init) {
vector<long long> dp(LIM + 1, -(1LL << 60));
if (Init.size() == 0) dp[0] = 0;
else {
for (int i = 0; i < min(LIM + 1, (long long)Init.size()); i++) dp[i] = Init[i];
}
// DP Start
for (int i = 0; i < N; i++) {
vector<long long> ndp(LIM + 1, -(1LL << 60));
long long kazu = i + 1;
for (int j = 0; j < kazu; j++) {
vector<pair<long long, long long>> maxi;
int cur = 0;
for (int k = j; k <= LIM; k += kazu) {
long long val = dp[k] - (k / kazu);
while (maxi.size() >= cur + 1) {
if (maxi[maxi.size() - 1].second <= val) maxi.pop_back();
else break;
}
maxi.push_back(make_pair(1LL * k, val));
if (maxi[cur].second >= -(1LL << 59)) ndp[k] = maxi[cur].second + (k / kazu);
while (cur < (int)maxi.size() && maxi[cur].first <= k - 1LL * kazu * List[i]) cur += 1;
}
}
dp = ndp;
}
// Return
return dp;
}
vector<long long> SolveDP2(long long N, long long LIM, vector<long long> List) {
vector<long long> dp(LIM + 1, -(1LL << 60));
vector<long long> ret(N, 0);
dp[0] = 0;
// DP Start
for (int i = N - 1; i >= 0; i--) {
for (int j = 1; j <= min(N, List[i]); j++) {
if (dp[(i + 1) * j] == -(1LL << 60)) ret[i] += 1;
else break;
}
vector<long long> ndp(LIM + 1, -(1LL << 60));
long long kazu = i + 1;
for (int j = 0; j < kazu; j++) {
vector<pair<long long, long long>> maxi;
int cur = 0;
for (int k = j; k <= LIM; k += kazu) {
long long val = dp[k] - (k / kazu);
while (maxi.size() >= cur + 1) {
if (maxi[maxi.size() - 1].second <= val) maxi.pop_back();
else break;
}
maxi.push_back(make_pair(1LL * k, val));
if (maxi[cur].second >= -(1LL << 59)) ndp[k] = maxi[cur].second + (k / kazu);
while (cur < (int)maxi.size() && maxi[cur].first <= k - 1LL * kazu * List[i]) cur += 1;
}
}
dp = ndp;
}
// Return
return ret;
}
long long Solve_Subtask6(long long M, long long L, vector<long long> A) {
vector<long long> M0(M, 0), M1(M, 0), M2(M, 0), M3(M, 0); // Minus
vector<long long> P0(M, 0), P1(M, 0), P2(M, 0), P3(M, 0); // Minus
// Step 1. First DP
for (int i = 0; i < M; i++) M0[i] = A[M - 1 - i];
for (int i = 0; i < M; i++) P0[i] = A[M + 1 + i];
M1 = SolveDP2(M, M * M + 1, M0);
P1 = SolveDP2(M, M * M + 1, P0);
// Step 2. Calculate Sum
long long sumM = 0; for (int i = 0; i < M; i++) sumM += 1LL * (i + 1) * (M0[i] - M1[i]);
long long sumP = 0; for (int i = 0; i < M; i++) sumP += 1LL * (i + 1) * (P0[i] - P1[i]);
long long Offset = M * M + 10LL * M;
long long Answer = 0;
long long Actual = 0;
if (sumP - sumM > L) sumP = sumM + L;
else sumM = sumP - L;
// Step 3. Greedy
for (int i = 0; i < M; i++) {
M2[i] = min(M0[i] - M1[i], max(0LL, sumM - Offset) / (i + 1));
Answer += M2[i];
sumM -= 1LL * (i + 1) * M2[i];
Actual -= 1LL * (i + 1) * M2[i];
M3[i] = M0[i] - M2[i];
}
for (int i = 0; i < M; i++) {
P2[i] = min(P0[i] - P1[i], max(0LL, sumP - Offset) / (i + 1));
Answer += P2[i];
sumP -= 1LL * (i + 1) * P2[i];
Actual += 1LL * (i + 1) * P2[i];
P3[i] = P0[i] - P2[i];
}
cout << "M0 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << M0[i]; } cout << "]" << endl;
cout << "M1 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << M1[i]; } cout << "]" << endl;
cout << "M2 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << M2[i]; } cout << "]" << endl;
cout << "M3 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << M3[i]; } cout << "]" << endl;
cout << "P0 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << P0[i]; } cout << "]" << endl;
cout << "P1 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << P1[i]; } cout << "]" << endl;
cout << "P2 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << P2[i]; } cout << "]" << endl;
cout << "P3 = ["; for (int i = 0; i < M; i++) { if (i) { cout << " "; } cout << P3[i]; } cout << "]" << endl;
// Step 4. Get Maximum
long long Maximum = Offset + M * M;
for (int i = 0; i < M; i++) Maximum += 1LL * (i + 1) * M1[i];
for (int i = 0; i < M; i++) Maximum += 1LL * (i + 1) * P1[i];
if (abs(Actual - L) > Maximum) return -1;
// Step 5. Get Answer
vector<long long> dp1 = SolveDP(M, Maximum, M3, vector<long long>{});
vector<long long> dp2 = vector<long long>(Maximum + 1, -(1LL << 60));
for (int i = 0; i <= Maximum; i++) dp2[Maximum - i] = dp1[i];
vector<long long> dp3 = SolveDP(M, Maximum + L - Actual, P3, dp2);
if (dp3[Maximum + L - Actual] == -(1LL << 60)) return -1;
return dp3[Maximum + L - Actual] + A[M] + Answer;
}
int main() {
// Input
long long M, L;
cin >> M >> L;
vector<long long> A(2 * M + 1, 0);
for (int i = 0; i <= 2 * M; i++) cin >> A[i];
// Output
long long Answer = Solve_Subtask6(M, L, A);
if (Answer == -1) cout << "impossible" << endl;
else cout << Answer << endl;
return 0;
}
Compilation message
vault.cpp: In function 'std::vector<long long int> SolveDP(long long int, long long int, std::vector<long long int>, std::vector<long long int>)':
vault.cpp:20:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | while (maxi.size() >= cur + 1) {
| ~~~~~~~~~~~~^~~~~~~~~~
vault.cpp: In function 'std::vector<long long int> SolveDP2(long long int, long long int, std::vector<long long int>)':
vault.cpp:54:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | while (maxi.size() >= cur + 1) {
| ~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
