Submission #860667

#	Time	Username	Problem	Language	Result	Execution time	Memory
860667		E869120	Uplifting Excursion (BOI22_vault)	C++14	90 / 100	5044 ms	70052 KiB

vault

#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_Easy(long long M, long long L, vector<long long> A) {
    if (L < 0) return -1;
    vector<long long> All;
    for (int i = M + 1; i <= 2 * M; i++) All.push_back(A[i]);
 
    // Step 1. First DP
    long long Load = 0;
    vector<long long> L0 = SolveDP2(M, M * M + 1, All);
    for (int i = 0; i < M; i++) Load += 1LL * (i + 1) * L0[i];
 
    // Step 2. Greedy
    vector<long long> L1(M, 0);
    vector<long long> L2(M, 0);
    long long rem = L - Load;
    long long ans = 0;
    for (int i = 0; i < M; i++) {
        if (rem < 0) continue;
        L1[i] = min(All[i] - L0[i], rem / (i + 1));
        ans += L1[i];
        rem -= 1LL * (i + 1) * L1[i];
    }
    for (int i = 0; i < M; i++) L2[i] = All[i] - L1[i];
    if (rem > M) return -1;
 
    // Step 2. DP
    vector<long long> dp = SolveDP(M, Load + rem, L2, vector<long long>{});
    if (dp[Load + rem] == -(1LL << 60)) return -1;
    return dp[Load + rem] + ans + A[M];
}

long long Solve_Hard(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]; 
    }
 
    // 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];
    
    // Judge if Subtask 5
    bool Subtask = true;
    for (int i = 0; i <  M; i++) {
        if (A[i] > 0) Subtask = false;
    }
 
    // Execution (Note that hard solution is not correct but passes in many cases)
    long long Answer = 0;
    if (Subtask == true) Answer = Solve_Easy(M, L, A);
    else Answer = Solve_Hard(M, L, A);
 
    // Output
    if (Answer == -1) cout << "impossible" << endl;
    else cout << Answer << endl;
    return 0;
}

Compilation message (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) {
      |                        ~~~~~~~~~~~~^~~~~~~~~~
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) {
      |                        ~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 0 / 10