제출 #860614

#제출 시각아이디문제언어결과실행 시간메모리
860614E869120Uplifting Excursion (BOI22_vault)C++14
20 / 100
1765 ms47416 KiB
#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_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]; } Cand1.push_back(make_pair(a1 + Baseln - rem1, cnt1)); // 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]; } Cand2.push_back(make_pair(a2 + Baseln - rem2, cnt2)); // 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; } // Execution if (Subtask2 == true) Solve_Subtask2(M, L, A); else Solve_Subtask3(M, L, A); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...