oj.uz

Submission #769122

# Submission time Handle Problem Language Result Execution time Memory
769122 2023-06-29T08:10:37 Z danikoynov Cat Exercise (JOI23_ho_t4) C++14
7 / 100
 27 ms 3016 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 5010;

int n, a[maxn], used[maxn][maxn], dp[maxn][maxn];

int rec(int left, int right)
{
    if (left == right)
        return 0;
        if (used[left][right])
            return dp[left][right];
        used[left][right] = 1;
    int pivot = left;
    for (int i = left + 1; i <= right; i ++)
        if (a[i] > a[pivot])
        pivot = i;

    int left_pivot = pivot - 1, right_pivot = right;

    for (int i = pivot - 1; i >= left; i --)
    {
        if (a[i] > a[left_pivot])
            left_pivot = i;
        dp[left][right] = max(dp[left][right], rec(i, pivot - 1) + pivot - left_pivot);
    }

    for (int i = pivot + 1; i <= right; i ++)
    {
        if (a[i] > a[right_pivot])
            right_pivot = i;
        dp[left][right] = max(dp[left][right], rec(pivot + 1, i) + right_pivot - pivot);
    }
    ///cout << left << " : " << right << " " << dp[left][right] << endl;
    return dp[left][right];
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
    }

    cout << rec(1, n) << endl;


}

int main()
{
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'int rec(int, int)':
Main.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if (left == right)
      |     ^~
Main.cpp:22:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |         if (used[left][right])
      |         ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 2964 KB Output is correct
12 Correct 25 ms 3016 KB Output is correct
13 Correct 25 ms 2940 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Incorrect 2 ms 2740 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 2964 KB Output is correct
12 Correct 25 ms 3016 KB Output is correct
13 Correct 25 ms 2940 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Incorrect 2 ms 2740 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 2964 KB Output is correct
12 Correct 25 ms 3016 KB Output is correct
13 Correct 25 ms 2940 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Incorrect 2 ms 2740 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 2964 KB Output is correct
12 Correct 25 ms 3016 KB Output is correct
13 Correct 25 ms 2940 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Incorrect 2 ms 2740 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 2 ms 1876 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 2964 KB Output is correct
12 Correct 25 ms 3016 KB Output is correct
13 Correct 25 ms 2940 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Incorrect 2 ms 2740 KB Output isn't correct
18 Halted 0 ms 0 KB -