oj.uz

Submission #804440

# Submission time Handle Problem Language Result Execution time Memory
804440 2023-08-03T08:43:57 Z 이동현(#10103) Fun Palace (CCO18_fun) C++17
3 / 25
 103 ms 94704 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 = 6004;
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 62 ms 94668 KB Output is correct
2 Correct 62 ms 94576 KB Output is correct
3 Correct 62 ms 94648 KB Output is correct
4 Correct 62 ms 94676 KB Output is correct
5 Correct 63 ms 94676 KB Output is correct
6 Correct 62 ms 94668 KB Output is correct
7 Correct 68 ms 94676 KB Output is correct
8 Correct 70 ms 94676 KB Output is correct
9 Correct 63 ms 94660 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94704 KB Output is correct
2 Correct 62 ms 94652 KB Output is correct
3 Correct 63 ms 94624 KB Output is correct
4 Correct 71 ms 94616 KB Output is correct
5 Correct 63 ms 94672 KB Output is correct
6 Correct 66 ms 94676 KB Output is correct
7 Incorrect 103 ms 94632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94668 KB Output is correct
2 Correct 62 ms 94576 KB Output is correct
3 Correct 62 ms 94648 KB Output is correct
4 Correct 62 ms 94676 KB Output is correct
5 Correct 63 ms 94676 KB Output is correct
6 Correct 62 ms 94668 KB Output is correct
7 Correct 68 ms 94676 KB Output is correct
8 Correct 70 ms 94676 KB Output is correct
9 Correct 63 ms 94660 KB Output is correct
10 Correct 63 ms 94676 KB Output is correct
11 Correct 74 ms 94672 KB Output is correct
12 Incorrect 71 ms 94676 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94668 KB Output is correct
2 Correct 62 ms 94576 KB Output is correct
3 Correct 62 ms 94648 KB Output is correct
4 Correct 62 ms 94676 KB Output is correct
5 Correct 63 ms 94676 KB Output is correct
6 Correct 62 ms 94668 KB Output is correct
7 Correct 68 ms 94676 KB Output is correct
8 Correct 70 ms 94676 KB Output is correct
9 Correct 63 ms 94660 KB Output is correct
10 Correct 62 ms 94704 KB Output is correct
11 Correct 62 ms 94652 KB Output is correct
12 Correct 63 ms 94624 KB Output is correct
13 Correct 71 ms 94616 KB Output is correct
14 Correct 63 ms 94672 KB Output is correct
15 Correct 66 ms 94676 KB Output is correct
16 Incorrect 103 ms 94632 KB Output isn't correct
17 Halted 0 ms 0 KB -