oj.uz

Submission #860615

# Submission time Handle Problem Language Result Execution time Memory
860615 2023-10-13T14:42:45 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1791 ms 47680 KB 
#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 + 3LL * M * M;
    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;
    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 - rem1, cnt1));

    // Step 5. Get Candidates for L2
    long long rem2 = a2;
    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 - 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;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45916 KB Output is correct
2 Correct 71 ms 46264 KB Output is correct
3 Correct 30 ms 47680 KB Output is correct
4 Correct 188 ms 45088 KB Output is correct
5 Correct 825 ms 45968 KB Output is correct
6 Correct 818 ms 44072 KB Output is correct
7 Correct 845 ms 45472 KB Output is correct
8 Correct 823 ms 45260 KB Output is correct
9 Correct 817 ms 44488 KB Output is correct
10 Correct 886 ms 46016 KB Output is correct
11 Correct 896 ms 46136 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45916 KB Output is correct
2 Correct 71 ms 46264 KB Output is correct
3 Correct 30 ms 47680 KB Output is correct
4 Correct 188 ms 45088 KB Output is correct
5 Correct 825 ms 45968 KB Output is correct
6 Correct 818 ms 44072 KB Output is correct
7 Correct 845 ms 45472 KB Output is correct
8 Correct 823 ms 45260 KB Output is correct
9 Correct 817 ms 44488 KB Output is correct
10 Correct 886 ms 46016 KB Output is correct
11 Correct 896 ms 46136 KB Output is correct
12 Correct 54 ms 44464 KB Output is correct
13 Correct 72 ms 45660 KB Output is correct
14 Correct 32 ms 44464 KB Output is correct
15 Correct 192 ms 45132 KB Output is correct
16 Correct 827 ms 45008 KB Output is correct
17 Correct 807 ms 44660 KB Output is correct
18 Correct 889 ms 46216 KB Output is correct
19 Correct 804 ms 45836 KB Output is correct
20 Correct 801 ms 44476 KB Output is correct
21 Correct 894 ms 45236 KB Output is correct
22 Correct 888 ms 45096 KB Output is correct
23 Correct 1622 ms 45364 KB Output is correct
24 Correct 1617 ms 44944 KB Output is correct
25 Correct 1703 ms 45064 KB Output is correct
26 Correct 1609 ms 47652 KB Output is correct
27 Correct 1651 ms 45600 KB Output is correct
28 Correct 1761 ms 45024 KB Output is correct
29 Correct 1791 ms 44616 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 44676 KB Output is correct
2 Correct 19 ms 2884 KB Output is correct
3 Incorrect 19 ms 2888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 44676 KB Output is correct
2 Correct 19 ms 2884 KB Output is correct
3 Incorrect 19 ms 2888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 44676 KB Output is correct
2 Correct 19 ms 2884 KB Output is correct
3 Incorrect 19 ms 2888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45916 KB Output is correct
2 Correct 71 ms 46264 KB Output is correct
3 Correct 30 ms 47680 KB Output is correct
4 Correct 188 ms 45088 KB Output is correct
5 Correct 825 ms 45968 KB Output is correct
6 Correct 818 ms 44072 KB Output is correct
7 Correct 845 ms 45472 KB Output is correct
8 Correct 823 ms 45260 KB Output is correct
9 Correct 817 ms 44488 KB Output is correct
10 Correct 886 ms 46016 KB Output is correct
11 Correct 896 ms 46136 KB Output is correct
12 Correct 210 ms 44676 KB Output is correct
13 Correct 19 ms 2884 KB Output is correct
14 Incorrect 19 ms 2888 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 44676 KB Output is correct
2 Correct 19 ms 2884 KB Output is correct
3 Incorrect 19 ms 2888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45916 KB Output is correct
2 Correct 71 ms 46264 KB Output is correct
3 Correct 30 ms 47680 KB Output is correct
4 Correct 188 ms 45088 KB Output is correct
5 Correct 825 ms 45968 KB Output is correct
6 Correct 818 ms 44072 KB Output is correct
7 Correct 845 ms 45472 KB Output is correct
8 Correct 823 ms 45260 KB Output is correct
9 Correct 817 ms 44488 KB Output is correct
10 Correct 886 ms 46016 KB Output is correct
11 Correct 896 ms 46136 KB Output is correct
12 Correct 54 ms 44464 KB Output is correct
13 Correct 72 ms 45660 KB Output is correct
14 Correct 32 ms 44464 KB Output is correct
15 Correct 192 ms 45132 KB Output is correct
16 Correct 827 ms 45008 KB Output is correct
17 Correct 807 ms 44660 KB Output is correct
18 Correct 889 ms 46216 KB Output is correct
19 Correct 804 ms 45836 KB Output is correct
20 Correct 801 ms 44476 KB Output is correct
21 Correct 894 ms 45236 KB Output is correct
22 Correct 888 ms 45096 KB Output is correct
23 Correct 1622 ms 45364 KB Output is correct
24 Correct 1617 ms 44944 KB Output is correct
25 Correct 1703 ms 45064 KB Output is correct
26 Correct 1609 ms 47652 KB Output is correct
27 Correct 1651 ms 45600 KB Output is correct
28 Correct 1761 ms 45024 KB Output is correct
29 Correct 1791 ms 44616 KB Output is correct
30 Correct 210 ms 44676 KB Output is correct
31 Correct 19 ms 2884 KB Output is correct
32 Incorrect 19 ms 2888 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 44676 KB Output is correct
2 Correct 19 ms 2884 KB Output is correct
3 Incorrect 19 ms 2888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45916 KB Output is correct
2 Correct 71 ms 46264 KB Output is correct
3 Correct 30 ms 47680 KB Output is correct
4 Correct 188 ms 45088 KB Output is correct
5 Correct 825 ms 45968 KB Output is correct
6 Correct 818 ms 44072 KB Output is correct
7 Correct 845 ms 45472 KB Output is correct
8 Correct 823 ms 45260 KB Output is correct
9 Correct 817 ms 44488 KB Output is correct
10 Correct 886 ms 46016 KB Output is correct
11 Correct 896 ms 46136 KB Output is correct
12 Correct 54 ms 44464 KB Output is correct
13 Correct 72 ms 45660 KB Output is correct
14 Correct 32 ms 44464 KB Output is correct
15 Correct 192 ms 45132 KB Output is correct
16 Correct 827 ms 45008 KB Output is correct
17 Correct 807 ms 44660 KB Output is correct
18 Correct 889 ms 46216 KB Output is correct
19 Correct 804 ms 45836 KB Output is correct
20 Correct 801 ms 44476 KB Output is correct
21 Correct 894 ms 45236 KB Output is correct
22 Correct 888 ms 45096 KB Output is correct
23 Correct 1622 ms 45364 KB Output is correct
24 Correct 1617 ms 44944 KB Output is correct
25 Correct 1703 ms 45064 KB Output is correct
26 Correct 1609 ms 47652 KB Output is correct
27 Correct 1651 ms 45600 KB Output is correct
28 Correct 1761 ms 45024 KB Output is correct
29 Correct 1791 ms 44616 KB Output is correct
30 Correct 210 ms 44676 KB Output is correct
31 Correct 19 ms 2884 KB Output is correct
32 Incorrect 19 ms 2888 KB Output isn't correct
33 Halted 0 ms 0 KB -