Submission #769122

#	Time	Username	Problem	Language	Result	Execution time	Memory
769122		danikoynov	Cat Exercise (JOI23_ho_t4)	C++14	7 / 100	27 ms	3016 KiB

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 (stderr)

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 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26