| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 860658 | E869120 | Uplifting Excursion (BOI22_vault) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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, (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;
}
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 = 4LL * M * 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];
}
// 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;
}