#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 < (int)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;
}
void Solve_Subtask2(long long M, long long L, vector<long long> A) {
// Step 1. Calculate
vector<long long> A1;
vector<long long> A2;
for (int i = M - 1; i >= 0; i--) A1.push_back(A[i]);
for (int i = M + 1; i <= 2 * M; i++) A2.push_back(A[i]);
vector<long long> DP1 = SolveDP(M, 700000, A1, vector<long long>{});
vector<long long> DP2 = SolveDP(M, 700000, A2, vector<long long>{});
// Step 2. Output
long long Answer = -(1LL << 60);
for (long long i = 0; i <= 700000LL - abs(L); i++) {
long long idx1 = i;
long long idx2 = i + abs(L); if (L < 0) swap(idx1, idx2);
Answer = max(Answer, DP1[idx1] + DP2[idx2]);
}
if (Answer < 0LL) cout << "impossible" << endl;
else cout << Answer + A[M] << endl;
}
void Solve_Subtask5(long long M, long long L, vector<long long> A) {
if (L < 0) { cout << "Impossible" << endl; return; }
// Step 1. Greedy
vector<long long> L1(M, 0);
vector<long long> L2(M, 0);
long long rem = L - M * M;
long long ans = 0;
for (int i = 0; i < M; i++) {
if (rem < 0) continue;
L1[i] = min(A[M + 1 + i], rem / (i + 1));
ans += L1[i];
rem -= 1LL * (i + 1) * L1[i];
}
for (int i = 0; i < M; i++) L2[i] = A[i] - L1[i];
if (rem > M) { cout << "impossible" << endl; return; }
// Step 2. DP
vector<long long> dp = SolveDP(M, M * M + rem, L2, vector<long long>{});
if (dp[M * M + rem] == -(1LL << 60)) { cout << "impossible" << endl; }
else cout << dp[M * M + rem] + ans + A[M] << endl;
}
void Solve_Subtask3(long long M, long long L, vector<long long> A) {
long long Baseln = (M + 1) * M * M / 2LL;
vector<long long> L1(M + 1, 0);
vector<long long> L2(M + 1, 0);
vector<long long> L3(M, 0);
vector<long long> L4(M, 0);
vector<long long> M1(M + 1, 0);
vector<long long> M2(M + 1, 0);
vector<pair<long long, long long>> Cand1; Cand1.push_back(make_pair(0, 0));
vector<pair<long long, long long>> Cand2; Cand2.push_back(make_pair(0, 0));
// Step 1. Set Up
for (int i = 0; i <= M - 1; i++) {
int idx = M - i;
long long Threshold = M;
L1[idx - 0] = A[i] - min(A[i], Threshold);
L3[idx - 1] = min(A[i], Threshold);
}
for (int i = M + 1; i <= 2 * M; i++) {
int idx = i - M;
long long Threshold = M;
L2[idx - 0] = A[i] - min(A[i], Threshold);
L4[idx - 1] = min(A[i], Threshold);
}
// Step 2. Base DP
vector<long long> dp1 = SolveDP(M, Baseln, L3, vector<long long>{});
vector<long long> dp2 = vector<long long>(Baseln + 1, -(1LL << 60));
for (int i = 0; i <= Baseln; i++) dp2[Baseln - i] = dp1[i];
vector<long long> dp3 = SolveDP(M, Baseln * 2, L4, dp2);
// Step 3. Get Theoritical Value
long long a1 = 0;
long long a2 = 0;
for (int i = 1; i <= M; i++) a1 += 1LL * i * L1[i];
for (int i = 1; i <= M; i++) a2 += 1LL * i * L2[i];
if (a2 - a1 > L) a2 = a1 + L;
else a1 = a2 - L;
if (a1 + Baseln < 0 || a2 + Baseln < 0) {
cout << "impossible" << endl;
return;
}
// Step 4. Get Candiates for L1
long long rem1 = a1 + Baseln;
long long cnt1 = 0;
for (int i = 1; i <= M; i++) {
M1[i] = min(L1[i], rem1 / i);
rem1 -= 1LL * i * M1[i];
cnt1 += M1[i];
}
for (int i = M; i >= 1; i--) {
for (long long j = 0; j < M1[i]; j++) {
Cand1.push_back(make_pair((a1 + Baseln) - rem1, cnt1));
rem1 += 1LL * i;
cnt1 -= 1LL;
if (rem1 > 2LL * Baseln) break;
}
if (rem1 > 2LL * Baseln) break;
}
// Step 5. Get Candidates for L2
long long rem2 = a2 + Baseln;
long long cnt2 = 0;
for (int i = 1; i <= M; i++) {
M2[i] = min(L2[i], rem2 / i);
rem2 -= 1LL * i * M2[i];
cnt2 += M2[i];
}
for (int i = M; i >= 1; i--) {
for (long long j = 0; j < M2[i]; j++) {
Cand2.push_back(make_pair((a2 + Baseln) - rem2, cnt2));
rem2 += 1LL * i;
cnt2 -= 1LL;
if (rem2 > 2LL * Baseln) break;
}
if (rem2 > 2LL * Baseln) break;
}
// cout << "L1 = "; for (int i = 1; i <= M; i++) cout << L1[i] << " "; cout << endl;
// cout << "L2 = "; for (int i = 1; i <= M; i++) cout << L2[i] << " "; cout << endl;
// cout << "Cand1 = "; for (int i = 0; i < Cand1.size(); i++) cout << "(" << Cand1[i].first << "," << Cand1[i].second << ") "; cout << endl;
// cout << "Cand2 = "; for (int i = 0; i < Cand2.size(); i++) cout << "(" << Cand2[i].first << "," << Cand2[i].second << ") "; cout << endl;
// Step 6. Brute Force
long long Answer = -(1LL << 60);
for (pair<long long, long long> v1 : Cand1) {
for (pair<long long, long long> v2 : Cand2) {
long long diff = L - (v2.first - v1.first);
if (diff < -Baseln || diff > Baseln) continue;
if (dp3[diff + Baseln] == -(1LL << 60)) continue;
Answer = max(Answer, v1.second + v2.second + dp3[diff + Baseln]);
}
}
// Step 7. Output
if (Answer == -(1LL << 60)) cout << "impossible" << endl;
else cout << Answer + A[M] << endl;
}
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];
// Judge if Subtask 2
bool Subtask2 = true;
if (M > 100) Subtask2 = false;
for (int i = 0; i <= 2 * M; i++) {
if (A[i] > 100) Subtask2 = false;
}
Subtask2 = false;
// Judge if Subtask 5
bool Subtask5 = true;
for (int i = 0; i < M; i++) {
if (A[i] > 0) Subtask5 = false;
}
// Execution
if (Subtask2 == true) Solve_Subtask2(M, L, A);
else if (Subtask5 == true) Solve_Subtask5(M, L, A);
else Solve_Subtask3(M, L, A);
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) {
| ~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
