oj.uz

Submission #860614

# Submission time Handle Problem Language Result Execution time Memory
860614 2023-10-13T14:41:31 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1765 ms 47416 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;
    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;
}

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 58 ms 45164 KB Output is correct
2 Correct 71 ms 45532 KB Output is correct
3 Correct 33 ms 44424 KB Output is correct
4 Correct 202 ms 44860 KB Output is correct
5 Correct 811 ms 45948 KB Output is correct
6 Correct 813 ms 45164 KB Output is correct
7 Correct 871 ms 44928 KB Output is correct
8 Correct 799 ms 46148 KB Output is correct
9 Correct 823 ms 45004 KB Output is correct
10 Correct 910 ms 45524 KB Output is correct
11 Correct 892 ms 45912 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 45164 KB Output is correct
2 Correct 71 ms 45532 KB Output is correct
3 Correct 33 ms 44424 KB Output is correct
4 Correct 202 ms 44860 KB Output is correct
5 Correct 811 ms 45948 KB Output is correct
6 Correct 813 ms 45164 KB Output is correct
7 Correct 871 ms 44928 KB Output is correct
8 Correct 799 ms 46148 KB Output is correct
9 Correct 823 ms 45004 KB Output is correct
10 Correct 910 ms 45524 KB Output is correct
11 Correct 892 ms 45912 KB Output is correct
12 Correct 52 ms 45368 KB Output is correct
13 Correct 72 ms 45300 KB Output is correct
14 Correct 32 ms 45712 KB Output is correct
15 Correct 189 ms 44740 KB Output is correct
16 Correct 813 ms 44248 KB Output is correct
17 Correct 803 ms 45180 KB Output is correct
18 Correct 863 ms 45152 KB Output is correct
19 Correct 810 ms 45100 KB Output is correct
20 Correct 827 ms 45804 KB Output is correct
21 Correct 910 ms 45016 KB Output is correct
22 Correct 886 ms 45904 KB Output is correct
23 Correct 1589 ms 44356 KB Output is correct
24 Correct 1607 ms 45528 KB Output is correct
25 Correct 1668 ms 45288 KB Output is correct
26 Correct 1604 ms 45304 KB Output is correct
27 Correct 1607 ms 44464 KB Output is correct
28 Correct 1723 ms 45140 KB Output is correct
29 Correct 1765 ms 46016 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 47416 KB Output is correct
2 Correct 15 ms 1784 KB Output is correct
3 Correct 16 ms 1924 KB Output is correct
4 Incorrect 15 ms 1788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 47416 KB Output is correct
2 Correct 15 ms 1784 KB Output is correct
3 Correct 16 ms 1924 KB Output is correct
4 Incorrect 15 ms 1788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 47416 KB Output is correct
2 Correct 15 ms 1784 KB Output is correct
3 Correct 16 ms 1924 KB Output is correct
4 Incorrect 15 ms 1788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 45164 KB Output is correct
2 Correct 71 ms 45532 KB Output is correct
3 Correct 33 ms 44424 KB Output is correct
4 Correct 202 ms 44860 KB Output is correct
5 Correct 811 ms 45948 KB Output is correct
6 Correct 813 ms 45164 KB Output is correct
7 Correct 871 ms 44928 KB Output is correct
8 Correct 799 ms 46148 KB Output is correct
9 Correct 823 ms 45004 KB Output is correct
10 Correct 910 ms 45524 KB Output is correct
11 Correct 892 ms 45912 KB Output is correct
12 Correct 191 ms 47416 KB Output is correct
13 Correct 15 ms 1784 KB Output is correct
14 Correct 16 ms 1924 KB Output is correct
15 Incorrect 15 ms 1788 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 47416 KB Output is correct
2 Correct 15 ms 1784 KB Output is correct
3 Correct 16 ms 1924 KB Output is correct
4 Incorrect 15 ms 1788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 45164 KB Output is correct
2 Correct 71 ms 45532 KB Output is correct
3 Correct 33 ms 44424 KB Output is correct
4 Correct 202 ms 44860 KB Output is correct
5 Correct 811 ms 45948 KB Output is correct
6 Correct 813 ms 45164 KB Output is correct
7 Correct 871 ms 44928 KB Output is correct
8 Correct 799 ms 46148 KB Output is correct
9 Correct 823 ms 45004 KB Output is correct
10 Correct 910 ms 45524 KB Output is correct
11 Correct 892 ms 45912 KB Output is correct
12 Correct 52 ms 45368 KB Output is correct
13 Correct 72 ms 45300 KB Output is correct
14 Correct 32 ms 45712 KB Output is correct
15 Correct 189 ms 44740 KB Output is correct
16 Correct 813 ms 44248 KB Output is correct
17 Correct 803 ms 45180 KB Output is correct
18 Correct 863 ms 45152 KB Output is correct
19 Correct 810 ms 45100 KB Output is correct
20 Correct 827 ms 45804 KB Output is correct
21 Correct 910 ms 45016 KB Output is correct
22 Correct 886 ms 45904 KB Output is correct
23 Correct 1589 ms 44356 KB Output is correct
24 Correct 1607 ms 45528 KB Output is correct
25 Correct 1668 ms 45288 KB Output is correct
26 Correct 1604 ms 45304 KB Output is correct
27 Correct 1607 ms 44464 KB Output is correct
28 Correct 1723 ms 45140 KB Output is correct
29 Correct 1765 ms 46016 KB Output is correct
30 Correct 191 ms 47416 KB Output is correct
31 Correct 15 ms 1784 KB Output is correct
32 Correct 16 ms 1924 KB Output is correct
33 Incorrect 15 ms 1788 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 47416 KB Output is correct
2 Correct 15 ms 1784 KB Output is correct
3 Correct 16 ms 1924 KB Output is correct
4 Incorrect 15 ms 1788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 45164 KB Output is correct
2 Correct 71 ms 45532 KB Output is correct
3 Correct 33 ms 44424 KB Output is correct
4 Correct 202 ms 44860 KB Output is correct
5 Correct 811 ms 45948 KB Output is correct
6 Correct 813 ms 45164 KB Output is correct
7 Correct 871 ms 44928 KB Output is correct
8 Correct 799 ms 46148 KB Output is correct
9 Correct 823 ms 45004 KB Output is correct
10 Correct 910 ms 45524 KB Output is correct
11 Correct 892 ms 45912 KB Output is correct
12 Correct 52 ms 45368 KB Output is correct
13 Correct 72 ms 45300 KB Output is correct
14 Correct 32 ms 45712 KB Output is correct
15 Correct 189 ms 44740 KB Output is correct
16 Correct 813 ms 44248 KB Output is correct
17 Correct 803 ms 45180 KB Output is correct
18 Correct 863 ms 45152 KB Output is correct
19 Correct 810 ms 45100 KB Output is correct
20 Correct 827 ms 45804 KB Output is correct
21 Correct 910 ms 45016 KB Output is correct
22 Correct 886 ms 45904 KB Output is correct
23 Correct 1589 ms 44356 KB Output is correct
24 Correct 1607 ms 45528 KB Output is correct
25 Correct 1668 ms 45288 KB Output is correct
26 Correct 1604 ms 45304 KB Output is correct
27 Correct 1607 ms 44464 KB Output is correct
28 Correct 1723 ms 45140 KB Output is correct
29 Correct 1765 ms 46016 KB Output is correct
30 Correct 191 ms 47416 KB Output is correct
31 Correct 15 ms 1784 KB Output is correct
32 Correct 16 ms 1924 KB Output is correct
33 Incorrect 15 ms 1788 KB Output isn't correct
34 Halted 0 ms 0 KB -