oj.uz

Submission #860646

# Submission time Handle Problem Language Result Execution time Memory
860646 2023-10-13T15:24:54 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1720 ms 47724 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, 0);
    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 + 1) * j] == -(1LL << 60)) ret[i] += 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 50 ms 45100 KB Output is correct
2 Correct 68 ms 45892 KB Output is correct
3 Correct 33 ms 45232 KB Output is correct
4 Correct 189 ms 45180 KB Output is correct
5 Correct 790 ms 44564 KB Output is correct
6 Correct 798 ms 45684 KB Output is correct
7 Correct 829 ms 44336 KB Output is correct
8 Correct 774 ms 45112 KB Output is correct
9 Correct 782 ms 45444 KB Output is correct
10 Correct 870 ms 45832 KB Output is correct
11 Correct 862 ms 45548 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45100 KB Output is correct
2 Correct 68 ms 45892 KB Output is correct
3 Correct 33 ms 45232 KB Output is correct
4 Correct 189 ms 45180 KB Output is correct
5 Correct 790 ms 44564 KB Output is correct
6 Correct 798 ms 45684 KB Output is correct
7 Correct 829 ms 44336 KB Output is correct
8 Correct 774 ms 45112 KB Output is correct
9 Correct 782 ms 45444 KB Output is correct
10 Correct 870 ms 45832 KB Output is correct
11 Correct 862 ms 45548 KB Output is correct
12 Correct 50 ms 46168 KB Output is correct
13 Correct 70 ms 45252 KB Output is correct
14 Correct 34 ms 45120 KB Output is correct
15 Correct 190 ms 47724 KB Output is correct
16 Correct 823 ms 47688 KB Output is correct
17 Correct 799 ms 45784 KB Output is correct
18 Correct 846 ms 47604 KB Output is correct
19 Correct 786 ms 45744 KB Output is correct
20 Correct 783 ms 44812 KB Output is correct
21 Correct 858 ms 45908 KB Output is correct
22 Correct 865 ms 44712 KB Output is correct
23 Correct 1589 ms 44452 KB Output is correct
24 Correct 1572 ms 44768 KB Output is correct
25 Correct 1635 ms 45400 KB Output is correct
26 Correct 1578 ms 44756 KB Output is correct
27 Correct 1548 ms 45464 KB Output is correct
28 Correct 1698 ms 47712 KB Output is correct
29 Correct 1720 ms 44824 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 45984 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 45984 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 45984 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45100 KB Output is correct
2 Correct 68 ms 45892 KB Output is correct
3 Correct 33 ms 45232 KB Output is correct
4 Correct 189 ms 45180 KB Output is correct
5 Correct 790 ms 44564 KB Output is correct
6 Correct 798 ms 45684 KB Output is correct
7 Correct 829 ms 44336 KB Output is correct
8 Correct 774 ms 45112 KB Output is correct
9 Correct 782 ms 45444 KB Output is correct
10 Correct 870 ms 45832 KB Output is correct
11 Correct 862 ms 45548 KB Output is correct
12 Correct 183 ms 45984 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 45984 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45100 KB Output is correct
2 Correct 68 ms 45892 KB Output is correct
3 Correct 33 ms 45232 KB Output is correct
4 Correct 189 ms 45180 KB Output is correct
5 Correct 790 ms 44564 KB Output is correct
6 Correct 798 ms 45684 KB Output is correct
7 Correct 829 ms 44336 KB Output is correct
8 Correct 774 ms 45112 KB Output is correct
9 Correct 782 ms 45444 KB Output is correct
10 Correct 870 ms 45832 KB Output is correct
11 Correct 862 ms 45548 KB Output is correct
12 Correct 50 ms 46168 KB Output is correct
13 Correct 70 ms 45252 KB Output is correct
14 Correct 34 ms 45120 KB Output is correct
15 Correct 190 ms 47724 KB Output is correct
16 Correct 823 ms 47688 KB Output is correct
17 Correct 799 ms 45784 KB Output is correct
18 Correct 846 ms 47604 KB Output is correct
19 Correct 786 ms 45744 KB Output is correct
20 Correct 783 ms 44812 KB Output is correct
21 Correct 858 ms 45908 KB Output is correct
22 Correct 865 ms 44712 KB Output is correct
23 Correct 1589 ms 44452 KB Output is correct
24 Correct 1572 ms 44768 KB Output is correct
25 Correct 1635 ms 45400 KB Output is correct
26 Correct 1578 ms 44756 KB Output is correct
27 Correct 1548 ms 45464 KB Output is correct
28 Correct 1698 ms 47712 KB Output is correct
29 Correct 1720 ms 44824 KB Output is correct
30 Correct 183 ms 45984 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 45984 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 45100 KB Output is correct
2 Correct 68 ms 45892 KB Output is correct
3 Correct 33 ms 45232 KB Output is correct
4 Correct 189 ms 45180 KB Output is correct
5 Correct 790 ms 44564 KB Output is correct
6 Correct 798 ms 45684 KB Output is correct
7 Correct 829 ms 44336 KB Output is correct
8 Correct 774 ms 45112 KB Output is correct
9 Correct 782 ms 45444 KB Output is correct
10 Correct 870 ms 45832 KB Output is correct
11 Correct 862 ms 45548 KB Output is correct
12 Correct 50 ms 46168 KB Output is correct
13 Correct 70 ms 45252 KB Output is correct
14 Correct 34 ms 45120 KB Output is correct
15 Correct 190 ms 47724 KB Output is correct
16 Correct 823 ms 47688 KB Output is correct
17 Correct 799 ms 45784 KB Output is correct
18 Correct 846 ms 47604 KB Output is correct
19 Correct 786 ms 45744 KB Output is correct
20 Correct 783 ms 44812 KB Output is correct
21 Correct 858 ms 45908 KB Output is correct
22 Correct 865 ms 44712 KB Output is correct
23 Correct 1589 ms 44452 KB Output is correct
24 Correct 1572 ms 44768 KB Output is correct
25 Correct 1635 ms 45400 KB Output is correct
26 Correct 1578 ms 44756 KB Output is correct
27 Correct 1548 ms 45464 KB Output is correct
28 Correct 1698 ms 47712 KB Output is correct
29 Correct 1720 ms 44824 KB Output is correct
30 Correct 183 ms 45984 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Halted 0 ms 0 KB -