oj.uz

Submission #875645

# Submission time Handle Problem Language Result Execution time Memory
875645 2023-11-20T10:04:44 Z hmm789 Cat Exercise (JOI23_ho_t4) C++14
21 / 100
 2000 ms 201296 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353
 
vector<int> adj[200000];
int mx[5000][5000];
int dfs(int x, int l, int r) {
    int ans = 0;
    if(x != l) ans = max(ans, dfs(mx[l][x-1], l, x-1)+x-mx[l][x-1]);
    if(x != r) ans = max(ans, dfs(mx[x+1][r], x+1, r)+mx[x+1][r]-x);
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, x, y;
    cin >> n;
    int p[n];
    for(int i = 0; i < n; i++) cin >> p[i];
    for(int i = 0; i < n-1; i++) {
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            if(i == j) mx[i][j] = i;
            else if(p[mx[i][j-1]] > p[j]) mx[i][j] = mx[i][j-1];
            else mx[i][j] = j;
        }
    }
    cout << dfs(mx[0][n-1], 0, n-1);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 7768 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 7768 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 18016 KB Output is correct
12 Correct 3 ms 18088 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 4 ms 18012 KB Output is correct
17 Correct 3 ms 18008 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 7768 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 18016 KB Output is correct
12 Correct 3 ms 18088 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 4 ms 18012 KB Output is correct
17 Correct 3 ms 18008 KB Output is correct
18 Correct 67 ms 201096 KB Output is correct
19 Correct 54 ms 201296 KB Output is correct
20 Correct 54 ms 201052 KB Output is correct
21 Correct 53 ms 201016 KB Output is correct
22 Correct 54 ms 201040 KB Output is correct
23 Correct 53 ms 201036 KB Output is correct
24 Correct 54 ms 201040 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 7768 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 18016 KB Output is correct
12 Correct 3 ms 18088 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 4 ms 18012 KB Output is correct
17 Correct 3 ms 18008 KB Output is correct
18 Correct 67 ms 201096 KB Output is correct
19 Correct 54 ms 201296 KB Output is correct
20 Correct 54 ms 201052 KB Output is correct
21 Correct 53 ms 201016 KB Output is correct
22 Correct 54 ms 201040 KB Output is correct
23 Correct 53 ms 201036 KB Output is correct
24 Correct 54 ms 201040 KB Output is correct
25 Correct 2 ms 7768 KB Output is correct
26 Incorrect 53 ms 201068 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 5724 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 7768 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 18016 KB Output is correct
12 Correct 3 ms 18088 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 4 ms 18012 KB Output is correct
17 Correct 3 ms 18008 KB Output is correct
18 Correct 67 ms 201096 KB Output is correct
19 Correct 54 ms 201296 KB Output is correct
20 Correct 54 ms 201052 KB Output is correct
21 Correct 53 ms 201016 KB Output is correct
22 Correct 54 ms 201040 KB Output is correct
23 Correct 53 ms 201036 KB Output is correct
24 Correct 54 ms 201040 KB Output is correct
25 Execution timed out 2056 ms 177628 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Incorrect 3 ms 13956 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 5724 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 7768 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 18016 KB Output is correct
12 Correct 3 ms 18088 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 4 ms 18012 KB Output is correct
17 Correct 3 ms 18008 KB Output is correct
18 Correct 67 ms 201096 KB Output is correct
19 Correct 54 ms 201296 KB Output is correct
20 Correct 54 ms 201052 KB Output is correct
21 Correct 53 ms 201016 KB Output is correct
22 Correct 54 ms 201040 KB Output is correct
23 Correct 53 ms 201036 KB Output is correct
24 Correct 54 ms 201040 KB Output is correct
25 Correct 2 ms 7768 KB Output is correct
26 Incorrect 53 ms 201068 KB Output isn't correct
27 Halted 0 ms 0 KB -