oj.uz

Submission #1040138

# Submission time Handle Problem Language Result Execution time Memory
1040138 2024-07-31T17:02:44 Z TAhmed33 Cat Exercise (JOI23_ho_t4) C++
21 / 100
 87 ms 166520 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 25;
int a[MAXN], n;
int dp[MAXN][MAXN];
int mx[MAXN][MAXN];
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int l = n; l >= 1; l--) {
        mx[l][l] = l;
        dp[l][l] = 0;
        for (int r = l + 1; r <= n; r++) {
            if (a[mx[l + 1][r]] > a[mx[l][r - 1]]) {
                mx[l][r] = mx[l + 1][r];
            } else {
                mx[l][r] = mx[l][r - 1];
            }
            int x = 0;
            if (mx[l][r] != r) {
                x = mx[mx[l][r] + 1][r] - mx[l][r];
            }
            int y = 0;
            if (mx[l][r] != l) {
                y = mx[l][r] - mx[l][mx[l][r] - 1];
            }
            dp[l][r] = max(x + dp[mx[l][r] + 1][r], y + dp[l][mx[l][r] - 1]);
        }
    }
    cout << dp[1][n] << '\n';
}       
signed main () {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12888 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12788 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12888 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12788 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 83 ms 166520 KB Output is correct
19 Correct 82 ms 165460 KB Output is correct
20 Correct 81 ms 166484 KB Output is correct
21 Correct 81 ms 165456 KB Output is correct
22 Correct 83 ms 166484 KB Output is correct
23 Correct 87 ms 165460 KB Output is correct
24 Correct 82 ms 166448 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12888 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12788 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 83 ms 166520 KB Output is correct
19 Correct 82 ms 165460 KB Output is correct
20 Correct 81 ms 166484 KB Output is correct
21 Correct 81 ms 165456 KB Output is correct
22 Correct 83 ms 166484 KB Output is correct
23 Correct 87 ms 165460 KB Output is correct
24 Correct 82 ms 166448 KB Output is correct
25 Correct 0 ms 2392 KB Output is correct
26 Incorrect 78 ms 165484 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12888 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12788 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 83 ms 166520 KB Output is correct
19 Correct 82 ms 165460 KB Output is correct
20 Correct 81 ms 166484 KB Output is correct
21 Correct 81 ms 165456 KB Output is correct
22 Correct 83 ms 166484 KB Output is correct
23 Correct 87 ms 165460 KB Output is correct
24 Correct 82 ms 166448 KB Output is correct
25 Runtime error 3 ms 732 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12888 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12788 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 83 ms 166520 KB Output is correct
19 Correct 82 ms 165460 KB Output is correct
20 Correct 81 ms 166484 KB Output is correct
21 Correct 81 ms 165456 KB Output is correct
22 Correct 83 ms 166484 KB Output is correct
23 Correct 87 ms 165460 KB Output is correct
24 Correct 82 ms 166448 KB Output is correct
25 Correct 0 ms 2392 KB Output is correct
26 Incorrect 78 ms 165484 KB Output isn't correct
27 Halted 0 ms 0 KB -