답안 #769122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769122	2023-06-29T08:10:37 Z	danikoynov	Cat Exercise (JOI23_ho_t4)	C++14	7 / 100	27 ms	3016 KB

Main

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-