oj.uz

Submission #860631

# Submission time Handle Problem Language Result Execution time Memory
860631 2023-10-13T14:58:49 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1850 ms 47676 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_Subtask5(long long M, long long L, vector<long long> A) {
    if (L < 0) { cout << "Impossible" << endl; return; }

    // Step 1. Greedy
    vector<long long> L1(M, 0);
    vector<long long> L2(M, 0);
    long long rem = L - M * M;
    long long ans = 0;
    for (int i = 0; i < M; i++) {
        if (rem < 0) continue;
        L1[i] = min(A[M + 1 + i], rem / (i + 1));
        ans += L1[i];
        rem -= 1LL * (i + 1) * L1[i];
    }
    for (int i = 0; i < M; i++) L2[i] += A[M + 1 + i];

    // Step 2. DP
    vector<long long> dp = SolveDP(M, M * M + rem, L2, vector<long long>{});
    if (dp[M * M + rem] == -(1LL << 60)) { cout << "impossible" << endl; }
    else cout << dp[M * M + rem] + ans + 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];
    }
    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)) 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;
    }

    // Judge if Subtask 5
    bool Subtask5 = true;
    for (int i = 0; i <  M; i++) {
        if (A[i] > 0) Subtask5 = false;
    }
 
    // Execution
    if (Subtask2 == true) Solve_Subtask2(M, L, A);
    else if (Subtask5 == true) Solve_Subtask5(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 57 ms 44628 KB Output is correct
2 Correct 79 ms 44288 KB Output is correct
3 Correct 32 ms 45304 KB Output is correct
4 Correct 196 ms 45768 KB Output is correct
5 Correct 864 ms 45088 KB Output is correct
6 Correct 845 ms 45824 KB Output is correct
7 Correct 876 ms 45484 KB Output is correct
8 Correct 890 ms 44704 KB Output is correct
9 Correct 869 ms 47676 KB Output is correct
10 Correct 899 ms 46092 KB Output is correct
11 Correct 928 ms 44244 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 44628 KB Output is correct
2 Correct 79 ms 44288 KB Output is correct
3 Correct 32 ms 45304 KB Output is correct
4 Correct 196 ms 45768 KB Output is correct
5 Correct 864 ms 45088 KB Output is correct
6 Correct 845 ms 45824 KB Output is correct
7 Correct 876 ms 45484 KB Output is correct
8 Correct 890 ms 44704 KB Output is correct
9 Correct 869 ms 47676 KB Output is correct
10 Correct 899 ms 46092 KB Output is correct
11 Correct 928 ms 44244 KB Output is correct
12 Correct 52 ms 44908 KB Output is correct
13 Correct 83 ms 44472 KB Output is correct
14 Correct 34 ms 46148 KB Output is correct
15 Correct 202 ms 44856 KB Output is correct
16 Correct 823 ms 44940 KB Output is correct
17 Correct 855 ms 45356 KB Output is correct
18 Correct 945 ms 44712 KB Output is correct
19 Correct 841 ms 45448 KB Output is correct
20 Correct 858 ms 44952 KB Output is correct
21 Correct 894 ms 45784 KB Output is correct
22 Correct 913 ms 46040 KB Output is correct
23 Correct 1692 ms 45404 KB Output is correct
24 Correct 1624 ms 45936 KB Output is correct
25 Correct 1797 ms 44908 KB Output is correct
26 Correct 1738 ms 45268 KB Output is correct
27 Correct 1709 ms 45452 KB Output is correct
28 Correct 1850 ms 45488 KB Output is correct
29 Correct 1805 ms 46248 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 44600 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 194 ms 44600 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 194 ms 44600 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 57 ms 44628 KB Output is correct
2 Correct 79 ms 44288 KB Output is correct
3 Correct 32 ms 45304 KB Output is correct
4 Correct 196 ms 45768 KB Output is correct
5 Correct 864 ms 45088 KB Output is correct
6 Correct 845 ms 45824 KB Output is correct
7 Correct 876 ms 45484 KB Output is correct
8 Correct 890 ms 44704 KB Output is correct
9 Correct 869 ms 47676 KB Output is correct
10 Correct 899 ms 46092 KB Output is correct
11 Correct 928 ms 44244 KB Output is correct
12 Correct 194 ms 44600 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 194 ms 44600 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 57 ms 44628 KB Output is correct
2 Correct 79 ms 44288 KB Output is correct
3 Correct 32 ms 45304 KB Output is correct
4 Correct 196 ms 45768 KB Output is correct
5 Correct 864 ms 45088 KB Output is correct
6 Correct 845 ms 45824 KB Output is correct
7 Correct 876 ms 45484 KB Output is correct
8 Correct 890 ms 44704 KB Output is correct
9 Correct 869 ms 47676 KB Output is correct
10 Correct 899 ms 46092 KB Output is correct
11 Correct 928 ms 44244 KB Output is correct
12 Correct 52 ms 44908 KB Output is correct
13 Correct 83 ms 44472 KB Output is correct
14 Correct 34 ms 46148 KB Output is correct
15 Correct 202 ms 44856 KB Output is correct
16 Correct 823 ms 44940 KB Output is correct
17 Correct 855 ms 45356 KB Output is correct
18 Correct 945 ms 44712 KB Output is correct
19 Correct 841 ms 45448 KB Output is correct
20 Correct 858 ms 44952 KB Output is correct
21 Correct 894 ms 45784 KB Output is correct
22 Correct 913 ms 46040 KB Output is correct
23 Correct 1692 ms 45404 KB Output is correct
24 Correct 1624 ms 45936 KB Output is correct
25 Correct 1797 ms 44908 KB Output is correct
26 Correct 1738 ms 45268 KB Output is correct
27 Correct 1709 ms 45452 KB Output is correct
28 Correct 1850 ms 45488 KB Output is correct
29 Correct 1805 ms 46248 KB Output is correct
30 Correct 194 ms 44600 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 194 ms 44600 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 57 ms 44628 KB Output is correct
2 Correct 79 ms 44288 KB Output is correct
3 Correct 32 ms 45304 KB Output is correct
4 Correct 196 ms 45768 KB Output is correct
5 Correct 864 ms 45088 KB Output is correct
6 Correct 845 ms 45824 KB Output is correct
7 Correct 876 ms 45484 KB Output is correct
8 Correct 890 ms 44704 KB Output is correct
9 Correct 869 ms 47676 KB Output is correct
10 Correct 899 ms 46092 KB Output is correct
11 Correct 928 ms 44244 KB Output is correct
12 Correct 52 ms 44908 KB Output is correct
13 Correct 83 ms 44472 KB Output is correct
14 Correct 34 ms 46148 KB Output is correct
15 Correct 202 ms 44856 KB Output is correct
16 Correct 823 ms 44940 KB Output is correct
17 Correct 855 ms 45356 KB Output is correct
18 Correct 945 ms 44712 KB Output is correct
19 Correct 841 ms 45448 KB Output is correct
20 Correct 858 ms 44952 KB Output is correct
21 Correct 894 ms 45784 KB Output is correct
22 Correct 913 ms 46040 KB Output is correct
23 Correct 1692 ms 45404 KB Output is correct
24 Correct 1624 ms 45936 KB Output is correct
25 Correct 1797 ms 44908 KB Output is correct
26 Correct 1738 ms 45268 KB Output is correct
27 Correct 1709 ms 45452 KB Output is correct
28 Correct 1850 ms 45488 KB Output is correct
29 Correct 1805 ms 46248 KB Output is correct
30 Correct 194 ms 44600 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Halted 0 ms 0 KB -