Submission #860642

#	Time	Username	Problem	Language	Result	Execution time	Memory
860642		E869120	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	1776 ms	47656 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 < (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, 1);
    dp[0] = 0;
 
    // DP Start
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= min(N, List[i]); j++) {
            if (dp[i * j] == -(1LL << 60)) ret[j] += 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_Subtask5(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, A);
    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_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) return -1;
    return Answer + A[M];
}

long long 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) return -1;
 
    // 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)) return -1;
    return Answer + A[M];
}
 
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;
    }

    // Judge if Subtask 5
    bool Subtask5 = true;
    for (int i = 0; i <  M; i++) {
        if (A[i] > 0) Subtask5 = false;
    }
 
    // Execution
    long long Answer = 0;
    if (Subtask2 == true) Answer = Solve_Subtask2(M, L, A);
    else if (Subtask5 == true) Answer = Solve_Subtask5(M, L, A);
    else Answer = Solve_Subtask3(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: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10