oj.uz

Submission #769123

# Submission time Handle Problem Language Result Execution time Memory
769123 2023-06-29T08:11:49 Z danikoynov Cat Exercise (JOI23_ho_t4) C++14
14 / 100
 2000 ms 17528 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 = pivot + 1;

    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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 264 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 264 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 3068 KB Output is correct
12 Correct 24 ms 3028 KB Output is correct
13 Correct 26 ms 3020 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 264 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 3068 KB Output is correct
12 Correct 24 ms 3028 KB Output is correct
13 Correct 26 ms 3020 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Execution timed out 2058 ms 17528 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 264 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 3068 KB Output is correct
12 Correct 24 ms 3028 KB Output is correct
13 Correct 26 ms 3020 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Execution timed out 2058 ms 17528 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 264 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 3068 KB Output is correct
12 Correct 24 ms 3028 KB Output is correct
13 Correct 26 ms 3020 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Execution timed out 2058 ms 17528 KB Time limit exceeded
19 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 1 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 264 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 27 ms 3068 KB Output is correct
12 Correct 24 ms 3028 KB Output is correct
13 Correct 26 ms 3020 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Execution timed out 2058 ms 17528 KB Time limit exceeded
19 Halted 0 ms 0 KB -