oj.uz

Submission #804437

# Submission time Handle Problem Language Result Execution time Memory
804437 2023-08-03T08:42:57 Z 이동현(#10103) Fun Palace (CCO18_fun) C++17
3 / 25
 62 ms 47540 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int fsz = 1004, ssz = 3004;
int dp[fsz][ssz][2];
int a[1004], b[1004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, e;
    cin >> n >> e;
    for(int i = 2; i <= n; ++i){
        cin >> a[i] >> b[i];
    }
    b[1] = e;
    a[n + 1] = (int)1e9;

    for(int i = 0; i < fsz; ++i){
        for(int j = 0; j < ssz; ++j){
            dp[i][j][0] = dp[i][j][1] = -(int)1e18;
        }
    }

    dp[n][0][1] = 0;
    for(int i = n; i >= 1; --i){
        for(int j = 0; j < ssz; ++j){
            dp[i][j][0] = max(dp[i][j][0], dp[i][j][1]);
            for(int k = 0; k <= a[i + 1]; ++k){
                int come = 0;
                if(a[i + 1] - k <= j - b[i + 1]){
                    come = j + k;
                }
                else{
                    come = k + max(0ll, j - b[i + 1]);
                }

                if(come >= ssz) break;
                
                dp[i - 1][come][k < b[i]] = max(dp[i - 1][come][k < b[i]], dp[i][j][1] + k);
                if(!k) dp[i - 1][come][1] = max(dp[i - 1][come][1], dp[i][j][0]);
            }

            // if(dp[i][j][0] != -(int)1e18) cout << i << ' ' << j << ' ' << dp[i][j][0] << endl;
        }
    }

    int ans = 0;
    for(int i = 0; i < e; ++i){
        ans = max(ans, dp[0][i][0]);
        ans = max(ans, dp[0][i][1]);
    }

    cout << ans << '\n';
    
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47516 KB Output is correct
2 Correct 24 ms 47536 KB Output is correct
3 Correct 26 ms 47504 KB Output is correct
4 Correct 24 ms 47444 KB Output is correct
5 Correct 24 ms 47508 KB Output is correct
6 Correct 33 ms 47456 KB Output is correct
7 Correct 26 ms 47520 KB Output is correct
8 Correct 24 ms 47536 KB Output is correct
9 Correct 28 ms 47536 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47444 KB Output is correct
2 Correct 24 ms 47496 KB Output is correct
3 Correct 25 ms 47540 KB Output is correct
4 Correct 25 ms 47528 KB Output is correct
5 Correct 27 ms 47444 KB Output is correct
6 Correct 24 ms 47444 KB Output is correct
7 Incorrect 62 ms 47532 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47516 KB Output is correct
2 Correct 24 ms 47536 KB Output is correct
3 Correct 26 ms 47504 KB Output is correct
4 Correct 24 ms 47444 KB Output is correct
5 Correct 24 ms 47508 KB Output is correct
6 Correct 33 ms 47456 KB Output is correct
7 Correct 26 ms 47520 KB Output is correct
8 Correct 24 ms 47536 KB Output is correct
9 Correct 28 ms 47536 KB Output is correct
10 Correct 25 ms 47456 KB Output is correct
11 Correct 25 ms 47432 KB Output is correct
12 Incorrect 24 ms 47468 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47516 KB Output is correct
2 Correct 24 ms 47536 KB Output is correct
3 Correct 26 ms 47504 KB Output is correct
4 Correct 24 ms 47444 KB Output is correct
5 Correct 24 ms 47508 KB Output is correct
6 Correct 33 ms 47456 KB Output is correct
7 Correct 26 ms 47520 KB Output is correct
8 Correct 24 ms 47536 KB Output is correct
9 Correct 28 ms 47536 KB Output is correct
10 Correct 33 ms 47444 KB Output is correct
11 Correct 24 ms 47496 KB Output is correct
12 Correct 25 ms 47540 KB Output is correct
13 Correct 25 ms 47528 KB Output is correct
14 Correct 27 ms 47444 KB Output is correct
15 Correct 24 ms 47444 KB Output is correct
16 Incorrect 62 ms 47532 KB Output isn't correct
17 Halted 0 ms 0 KB -