oj.uz

Submission #860642

# Submission time Handle Problem Language Result Execution time Memory
860642 2023-10-13T15:17:00 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1776 ms 47656 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;
}

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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 44544 KB Output is correct
2 Correct 66 ms 44056 KB Output is correct
3 Correct 32 ms 46224 KB Output is correct
4 Correct 190 ms 45088 KB Output is correct
5 Correct 800 ms 46136 KB Output is correct
6 Correct 803 ms 44628 KB Output is correct
7 Correct 843 ms 46076 KB Output is correct
8 Correct 804 ms 44612 KB Output is correct
9 Correct 798 ms 45556 KB Output is correct
10 Correct 868 ms 45316 KB Output is correct
11 Correct 873 ms 45276 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 44544 KB Output is correct
2 Correct 66 ms 44056 KB Output is correct
3 Correct 32 ms 46224 KB Output is correct
4 Correct 190 ms 45088 KB Output is correct
5 Correct 800 ms 46136 KB Output is correct
6 Correct 803 ms 44628 KB Output is correct
7 Correct 843 ms 46076 KB Output is correct
8 Correct 804 ms 44612 KB Output is correct
9 Correct 798 ms 45556 KB Output is correct
10 Correct 868 ms 45316 KB Output is correct
11 Correct 873 ms 45276 KB Output is correct
12 Correct 49 ms 47656 KB Output is correct
13 Correct 70 ms 44476 KB Output is correct
14 Correct 32 ms 44204 KB Output is correct
15 Correct 187 ms 45936 KB Output is correct
16 Correct 777 ms 45364 KB Output is correct
17 Correct 773 ms 45180 KB Output is correct
18 Correct 831 ms 44444 KB Output is correct
19 Correct 786 ms 45312 KB Output is correct
20 Correct 798 ms 45084 KB Output is correct
21 Correct 870 ms 45484 KB Output is correct
22 Correct 865 ms 44400 KB Output is correct
23 Correct 1554 ms 44952 KB Output is correct
24 Correct 1559 ms 46168 KB Output is correct
25 Correct 1668 ms 45644 KB Output is correct
26 Correct 1566 ms 46160 KB Output is correct
27 Correct 1565 ms 45720 KB Output is correct
28 Correct 1742 ms 45820 KB Output is correct
29 Correct 1776 ms 44628 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 45880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 186 ms 45880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 186 ms 45880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 51 ms 44544 KB Output is correct
2 Correct 66 ms 44056 KB Output is correct
3 Correct 32 ms 46224 KB Output is correct
4 Correct 190 ms 45088 KB Output is correct
5 Correct 800 ms 46136 KB Output is correct
6 Correct 803 ms 44628 KB Output is correct
7 Correct 843 ms 46076 KB Output is correct
8 Correct 804 ms 44612 KB Output is correct
9 Correct 798 ms 45556 KB Output is correct
10 Correct 868 ms 45316 KB Output is correct
11 Correct 873 ms 45276 KB Output is correct
12 Correct 186 ms 45880 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 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 186 ms 45880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 51 ms 44544 KB Output is correct
2 Correct 66 ms 44056 KB Output is correct
3 Correct 32 ms 46224 KB Output is correct
4 Correct 190 ms 45088 KB Output is correct
5 Correct 800 ms 46136 KB Output is correct
6 Correct 803 ms 44628 KB Output is correct
7 Correct 843 ms 46076 KB Output is correct
8 Correct 804 ms 44612 KB Output is correct
9 Correct 798 ms 45556 KB Output is correct
10 Correct 868 ms 45316 KB Output is correct
11 Correct 873 ms 45276 KB Output is correct
12 Correct 49 ms 47656 KB Output is correct
13 Correct 70 ms 44476 KB Output is correct
14 Correct 32 ms 44204 KB Output is correct
15 Correct 187 ms 45936 KB Output is correct
16 Correct 777 ms 45364 KB Output is correct
17 Correct 773 ms 45180 KB Output is correct
18 Correct 831 ms 44444 KB Output is correct
19 Correct 786 ms 45312 KB Output is correct
20 Correct 798 ms 45084 KB Output is correct
21 Correct 870 ms 45484 KB Output is correct
22 Correct 865 ms 44400 KB Output is correct
23 Correct 1554 ms 44952 KB Output is correct
24 Correct 1559 ms 46168 KB Output is correct
25 Correct 1668 ms 45644 KB Output is correct
26 Correct 1566 ms 46160 KB Output is correct
27 Correct 1565 ms 45720 KB Output is correct
28 Correct 1742 ms 45820 KB Output is correct
29 Correct 1776 ms 44628 KB Output is correct
30 Correct 186 ms 45880 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Incorrect 1 ms 348 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 186 ms 45880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 51 ms 44544 KB Output is correct
2 Correct 66 ms 44056 KB Output is correct
3 Correct 32 ms 46224 KB Output is correct
4 Correct 190 ms 45088 KB Output is correct
5 Correct 800 ms 46136 KB Output is correct
6 Correct 803 ms 44628 KB Output is correct
7 Correct 843 ms 46076 KB Output is correct
8 Correct 804 ms 44612 KB Output is correct
9 Correct 798 ms 45556 KB Output is correct
10 Correct 868 ms 45316 KB Output is correct
11 Correct 873 ms 45276 KB Output is correct
12 Correct 49 ms 47656 KB Output is correct
13 Correct 70 ms 44476 KB Output is correct
14 Correct 32 ms 44204 KB Output is correct
15 Correct 187 ms 45936 KB Output is correct
16 Correct 777 ms 45364 KB Output is correct
17 Correct 773 ms 45180 KB Output is correct
18 Correct 831 ms 44444 KB Output is correct
19 Correct 786 ms 45312 KB Output is correct
20 Correct 798 ms 45084 KB Output is correct
21 Correct 870 ms 45484 KB Output is correct
22 Correct 865 ms 44400 KB Output is correct
23 Correct 1554 ms 44952 KB Output is correct
24 Correct 1559 ms 46168 KB Output is correct
25 Correct 1668 ms 45644 KB Output is correct
26 Correct 1566 ms 46160 KB Output is correct
27 Correct 1565 ms 45720 KB Output is correct
28 Correct 1742 ms 45820 KB Output is correct
29 Correct 1776 ms 44628 KB Output is correct
30 Correct 186 ms 45880 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Incorrect 1 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -