Submission #1086927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086927		vjudge1	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	1153 ms	4448 KiB

vault

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int const M = 350;
int const MM = M*M;
int const off = 340;
int const off2 = off*off;
ll A[2*M];
ll dp[2][2*MM];

int m; ll l;

int main() {
    cin >> m >> l;
    for (int i = -m; i <= m; ++i) cin >> A[i+off];
    ll zz = -l;
    for (int i = -m; i <= m; ++i) {
        zz += A[i+off] * i;
    }
    if (zz < 0) {
        l = -l;
        for (int i = -m; i < 0; ++i) {
            int j = -i;
            int idx = i+off, idx2 = j+off;
            swap(A[idx], A[idx2]);
        }
    }

    ll itm = 0;
    memset(dp, 0xc3, sizeof dp);
    dp[0][off2] = 0;
    int idp = 1;

    for (int i = -m; i <= m; ++i) {
        ll take = i <= 0 ? A[i+off] : min(A[i+off], max(0LL, l / i));
        l -= take * i;
        A[i+off] -= take;
        itm += take;

        memcpy(dp[idp], dp[idp^1], sizeof dp[idp]);
        if (i != 0) {
            // try_add_to_dp A[i+off]
            for (int j = -m*m; j < -m*m+i; ++j) {
                deque<int> dq;
                dq.emplace_back(j);
                for (int k = j + i; k <= m*m; k += i) {
                    while (dq.size() && (k-dq.front())/i > A[i+off]) dq.pop_front();
                    while (dq.size() && dp[idp^1][k+off2] >= dp[idp^1][dq.back()+off2]+(k-dq.back())/i) dq.pop_back();
                    dq.emplace_back(k);

                    if (dq.size()) dp[idp][k+off2] = max(dp[idp][k+off2], 
                        dp[idp^1][dq.front()+off2] + (k-dq.front())/i);
                }
                //for (int k = 1; (k <= A[i+off]) && (j-k*i>=-m*m) && (j-k*i<=m*m); ++k) {
                //    dp[idp][j+off2] = max(dp[idp][j+off2], dp[idp^1][j-k*i+off2] + k);
                //}
            }
            memcpy(dp[idp^1], dp[idp], sizeof dp[idp]);
            // try_delete_from_dp take
            if (i > 0) {
                for (int j = m*m; j > m*m-i; --j) {
                    deque<int> dq;
                    dq.emplace_back(j);
                    for (int k = j-i; k >= -m*m; k -= i) {
                        while (dq.size() && (dq.front()-k)/i > take) dq.pop_front();
                        while (dq.size() && dp[idp^1][k+off2] >= dp[idp^1][dq.back()+off2]-(dq.back()-k)/i)
                            dq.pop_back();
                        dq.emplace_back(k);
                        if (dq.size()) dp[idp][k+off2] = max(dp[idp][k+off2],
                            dp[idp^1][dq.front()+off2] - (dq.front()-k)/i);
                    }
                    //for (int k = 1; (k <= take) && (j+k*i>=-m*m) && (j+k*i<=m*m); ++k) {
                    //    dp[idp][j+off2] = max(dp[idp][j+off2], dp[idp^1][j+k*i+off2] - k);
                    //}
                    }
            }
            else {
                for (int j = -m*m; j < -m*m+i; ++j) {
                    deque<int> dq;
                    dq.emplace_back(j);
                    for (int k = j + i; k <= m*m; k += i) {
                        while (dq.size() && (dq.front()-k)/i > take) dq.pop_front();
                        while (dq.size() && dp[idp^1][k+off2] >= dp[idp^1][dq.back()+off2]-(dq.back()-k)/i) 
                            dq.pop_back();
                        dq.emplace_back(k);

                        if (dq.size()) dp[idp][k+off2] = max(dp[idp][k+off2], 
                            dp[idp^1][dq.front()+off2] - (dq.front()-k)/i);
                    }
                }
            }
        }
        idp ^= 1;
    }
    idp ^= 1;
    if (l < -m*m || l > m*m || dp[idp][l+off2] < -1e9) {
        cout << "impossible\n";
    }
    else {
        cout << (dp[idp][l+off2] + itm) << '\n';
    }
}

• 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: 10 / 10