oj.uz

Submission #860597

# Submission time Handle Problem Language Result Execution time Memory
860597 2023-10-13T12:55:40 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1759 ms 47556 KB 
#include <bits/stdc++.h>
using namespace std;

vector<long long> solve(long long N, long long LIM, vector<long long> List) {
    vector<long long> dp(LIM + 1, -(1LL << 60));
    dp[0] = 0;

    // 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;
}

int main() {
    // Step 1. 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];

    // Step 2. 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 = solve(M, 700000, A1);
    vector<long long> DP2 = solve(M, 700000, A2);

    // Step 3. 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;
    return 0;
}

Compilation message

vault.cpp: In function 'std::vector<long long int> solve(long long int, long long int, std::vector<long long int>)':
vault.cpp:17: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]
   17 |                 while (maxi.size() >= cur + 1) {
      |                        ~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 44932 KB Output is correct
2 Correct 70 ms 44824 KB Output is correct
3 Correct 32 ms 44980 KB Output is correct
4 Correct 188 ms 47464 KB Output is correct
5 Correct 809 ms 46188 KB Output is correct
6 Correct 803 ms 44412 KB Output is correct
7 Correct 853 ms 45280 KB Output is correct
8 Correct 817 ms 44572 KB Output is correct
9 Correct 787 ms 46040 KB Output is correct
10 Correct 883 ms 44252 KB Output is correct
11 Correct 863 ms 46216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 44932 KB Output is correct
2 Correct 70 ms 44824 KB Output is correct
3 Correct 32 ms 44980 KB Output is correct
4 Correct 188 ms 47464 KB Output is correct
5 Correct 809 ms 46188 KB Output is correct
6 Correct 803 ms 44412 KB Output is correct
7 Correct 853 ms 45280 KB Output is correct
8 Correct 817 ms 44572 KB Output is correct
9 Correct 787 ms 46040 KB Output is correct
10 Correct 883 ms 44252 KB Output is correct
11 Correct 863 ms 46216 KB Output is correct
12 Correct 51 ms 45180 KB Output is correct
13 Correct 69 ms 47556 KB Output is correct
14 Correct 33 ms 45536 KB Output is correct
15 Correct 188 ms 44768 KB Output is correct
16 Correct 809 ms 45528 KB Output is correct
17 Correct 810 ms 44496 KB Output is correct
18 Correct 837 ms 44572 KB Output is correct
19 Correct 803 ms 45192 KB Output is correct
20 Correct 786 ms 44332 KB Output is correct
21 Correct 881 ms 45392 KB Output is correct
22 Correct 861 ms 44244 KB Output is correct
23 Correct 1615 ms 44360 KB Output is correct
24 Correct 1569 ms 44820 KB Output is correct
25 Correct 1649 ms 45516 KB Output is correct
26 Correct 1576 ms 45364 KB Output is correct
27 Correct 1571 ms 44868 KB Output is correct
28 Correct 1759 ms 44412 KB Output is correct
29 Correct 1695 ms 44264 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 44976 KB Output is correct
2 Incorrect 521 ms 45904 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 195 ms 44976 KB Output is correct
2 Incorrect 521 ms 45904 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 195 ms 44976 KB Output is correct
2 Incorrect 521 ms 45904 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 52 ms 44932 KB Output is correct
2 Correct 70 ms 44824 KB Output is correct
3 Correct 32 ms 44980 KB Output is correct
4 Correct 188 ms 47464 KB Output is correct
5 Correct 809 ms 46188 KB Output is correct
6 Correct 803 ms 44412 KB Output is correct
7 Correct 853 ms 45280 KB Output is correct
8 Correct 817 ms 44572 KB Output is correct
9 Correct 787 ms 46040 KB Output is correct
10 Correct 883 ms 44252 KB Output is correct
11 Correct 863 ms 46216 KB Output is correct
12 Correct 195 ms 44976 KB Output is correct
13 Incorrect 521 ms 45904 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 195 ms 44976 KB Output is correct
2 Incorrect 521 ms 45904 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 52 ms 44932 KB Output is correct
2 Correct 70 ms 44824 KB Output is correct
3 Correct 32 ms 44980 KB Output is correct
4 Correct 188 ms 47464 KB Output is correct
5 Correct 809 ms 46188 KB Output is correct
6 Correct 803 ms 44412 KB Output is correct
7 Correct 853 ms 45280 KB Output is correct
8 Correct 817 ms 44572 KB Output is correct
9 Correct 787 ms 46040 KB Output is correct
10 Correct 883 ms 44252 KB Output is correct
11 Correct 863 ms 46216 KB Output is correct
12 Correct 51 ms 45180 KB Output is correct
13 Correct 69 ms 47556 KB Output is correct
14 Correct 33 ms 45536 KB Output is correct
15 Correct 188 ms 44768 KB Output is correct
16 Correct 809 ms 45528 KB Output is correct
17 Correct 810 ms 44496 KB Output is correct
18 Correct 837 ms 44572 KB Output is correct
19 Correct 803 ms 45192 KB Output is correct
20 Correct 786 ms 44332 KB Output is correct
21 Correct 881 ms 45392 KB Output is correct
22 Correct 861 ms 44244 KB Output is correct
23 Correct 1615 ms 44360 KB Output is correct
24 Correct 1569 ms 44820 KB Output is correct
25 Correct 1649 ms 45516 KB Output is correct
26 Correct 1576 ms 45364 KB Output is correct
27 Correct 1571 ms 44868 KB Output is correct
28 Correct 1759 ms 44412 KB Output is correct
29 Correct 1695 ms 44264 KB Output is correct
30 Correct 195 ms 44976 KB Output is correct
31 Incorrect 521 ms 45904 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 195 ms 44976 KB Output is correct
2 Incorrect 521 ms 45904 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 52 ms 44932 KB Output is correct
2 Correct 70 ms 44824 KB Output is correct
3 Correct 32 ms 44980 KB Output is correct
4 Correct 188 ms 47464 KB Output is correct
5 Correct 809 ms 46188 KB Output is correct
6 Correct 803 ms 44412 KB Output is correct
7 Correct 853 ms 45280 KB Output is correct
8 Correct 817 ms 44572 KB Output is correct
9 Correct 787 ms 46040 KB Output is correct
10 Correct 883 ms 44252 KB Output is correct
11 Correct 863 ms 46216 KB Output is correct
12 Correct 51 ms 45180 KB Output is correct
13 Correct 69 ms 47556 KB Output is correct
14 Correct 33 ms 45536 KB Output is correct
15 Correct 188 ms 44768 KB Output is correct
16 Correct 809 ms 45528 KB Output is correct
17 Correct 810 ms 44496 KB Output is correct
18 Correct 837 ms 44572 KB Output is correct
19 Correct 803 ms 45192 KB Output is correct
20 Correct 786 ms 44332 KB Output is correct
21 Correct 881 ms 45392 KB Output is correct
22 Correct 861 ms 44244 KB Output is correct
23 Correct 1615 ms 44360 KB Output is correct
24 Correct 1569 ms 44820 KB Output is correct
25 Correct 1649 ms 45516 KB Output is correct
26 Correct 1576 ms 45364 KB Output is correct
27 Correct 1571 ms 44868 KB Output is correct
28 Correct 1759 ms 44412 KB Output is correct
29 Correct 1695 ms 44264 KB Output is correct
30 Correct 195 ms 44976 KB Output is correct
31 Incorrect 521 ms 45904 KB Output isn't correct
32 Halted 0 ms 0 KB -