oj.uz

Submission #860643

# Submission time Handle Problem Language Result Execution time Memory
860643 2023-10-13T15:19:00 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1736 ms 47716 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, All);
    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 52 ms 45480 KB Output is correct
2 Correct 72 ms 44556 KB Output is correct
3 Correct 34 ms 45512 KB Output is correct
4 Correct 187 ms 47484 KB Output is correct
5 Correct 791 ms 45408 KB Output is correct
6 Correct 813 ms 44904 KB Output is correct
7 Correct 837 ms 45384 KB Output is correct
8 Correct 801 ms 45956 KB Output is correct
9 Correct 815 ms 44432 KB Output is correct
10 Correct 882 ms 44792 KB Output is correct
11 Correct 870 ms 46100 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45480 KB Output is correct
2 Correct 72 ms 44556 KB Output is correct
3 Correct 34 ms 45512 KB Output is correct
4 Correct 187 ms 47484 KB Output is correct
5 Correct 791 ms 45408 KB Output is correct
6 Correct 813 ms 44904 KB Output is correct
7 Correct 837 ms 45384 KB Output is correct
8 Correct 801 ms 45956 KB Output is correct
9 Correct 815 ms 44432 KB Output is correct
10 Correct 882 ms 44792 KB Output is correct
11 Correct 870 ms 46100 KB Output is correct
12 Correct 53 ms 45252 KB Output is correct
13 Correct 69 ms 44256 KB Output is correct
14 Correct 34 ms 46148 KB Output is correct
15 Correct 189 ms 47716 KB Output is correct
16 Correct 807 ms 44952 KB Output is correct
17 Correct 816 ms 44940 KB Output is correct
18 Correct 846 ms 46196 KB Output is correct
19 Correct 788 ms 44320 KB Output is correct
20 Correct 810 ms 45016 KB Output is correct
21 Correct 873 ms 46060 KB Output is correct
22 Correct 898 ms 45324 KB Output is correct
23 Correct 1602 ms 45344 KB Output is correct
24 Correct 1579 ms 45792 KB Output is correct
25 Correct 1697 ms 44696 KB Output is correct
26 Correct 1594 ms 47632 KB Output is correct
27 Correct 1592 ms 45480 KB Output is correct
28 Correct 1720 ms 47648 KB Output is correct
29 Correct 1736 ms 44732 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 45136 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 193 ms 45136 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 193 ms 45136 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 52 ms 45480 KB Output is correct
2 Correct 72 ms 44556 KB Output is correct
3 Correct 34 ms 45512 KB Output is correct
4 Correct 187 ms 47484 KB Output is correct
5 Correct 791 ms 45408 KB Output is correct
6 Correct 813 ms 44904 KB Output is correct
7 Correct 837 ms 45384 KB Output is correct
8 Correct 801 ms 45956 KB Output is correct
9 Correct 815 ms 44432 KB Output is correct
10 Correct 882 ms 44792 KB Output is correct
11 Correct 870 ms 46100 KB Output is correct
12 Correct 193 ms 45136 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 193 ms 45136 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 52 ms 45480 KB Output is correct
2 Correct 72 ms 44556 KB Output is correct
3 Correct 34 ms 45512 KB Output is correct
4 Correct 187 ms 47484 KB Output is correct
5 Correct 791 ms 45408 KB Output is correct
6 Correct 813 ms 44904 KB Output is correct
7 Correct 837 ms 45384 KB Output is correct
8 Correct 801 ms 45956 KB Output is correct
9 Correct 815 ms 44432 KB Output is correct
10 Correct 882 ms 44792 KB Output is correct
11 Correct 870 ms 46100 KB Output is correct
12 Correct 53 ms 45252 KB Output is correct
13 Correct 69 ms 44256 KB Output is correct
14 Correct 34 ms 46148 KB Output is correct
15 Correct 189 ms 47716 KB Output is correct
16 Correct 807 ms 44952 KB Output is correct
17 Correct 816 ms 44940 KB Output is correct
18 Correct 846 ms 46196 KB Output is correct
19 Correct 788 ms 44320 KB Output is correct
20 Correct 810 ms 45016 KB Output is correct
21 Correct 873 ms 46060 KB Output is correct
22 Correct 898 ms 45324 KB Output is correct
23 Correct 1602 ms 45344 KB Output is correct
24 Correct 1579 ms 45792 KB Output is correct
25 Correct 1697 ms 44696 KB Output is correct
26 Correct 1594 ms 47632 KB Output is correct
27 Correct 1592 ms 45480 KB Output is correct
28 Correct 1720 ms 47648 KB Output is correct
29 Correct 1736 ms 44732 KB Output is correct
30 Correct 193 ms 45136 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 193 ms 45136 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 52 ms 45480 KB Output is correct
2 Correct 72 ms 44556 KB Output is correct
3 Correct 34 ms 45512 KB Output is correct
4 Correct 187 ms 47484 KB Output is correct
5 Correct 791 ms 45408 KB Output is correct
6 Correct 813 ms 44904 KB Output is correct
7 Correct 837 ms 45384 KB Output is correct
8 Correct 801 ms 45956 KB Output is correct
9 Correct 815 ms 44432 KB Output is correct
10 Correct 882 ms 44792 KB Output is correct
11 Correct 870 ms 46100 KB Output is correct
12 Correct 53 ms 45252 KB Output is correct
13 Correct 69 ms 44256 KB Output is correct
14 Correct 34 ms 46148 KB Output is correct
15 Correct 189 ms 47716 KB Output is correct
16 Correct 807 ms 44952 KB Output is correct
17 Correct 816 ms 44940 KB Output is correct
18 Correct 846 ms 46196 KB Output is correct
19 Correct 788 ms 44320 KB Output is correct
20 Correct 810 ms 45016 KB Output is correct
21 Correct 873 ms 46060 KB Output is correct
22 Correct 898 ms 45324 KB Output is correct
23 Correct 1602 ms 45344 KB Output is correct
24 Correct 1579 ms 45792 KB Output is correct
25 Correct 1697 ms 44696 KB Output is correct
26 Correct 1594 ms 47632 KB Output is correct
27 Correct 1592 ms 45480 KB Output is correct
28 Correct 1720 ms 47648 KB Output is correct
29 Correct 1736 ms 44732 KB Output is correct
30 Correct 193 ms 45136 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 -