Submission #944924

#	Time	Username	Problem	Language	Result	Execution time	Memory
944924		vladilius	Cat Exercise (JOI23_ho_t4)	C++17	21 / 100	2047 ms	16364 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int msz = 2e5 + 5;

vector<int> g[msz];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1);
    int s = 0;
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        if (a[i] == n){
            s = i;
        }
    }
    for (int i = 1; i < n; i++){
        int a, b; cin>>a>>b;
        if (a != i || b != (i + 1)){
            return 0;
        }
        g[a].push_back(b);
        g[b].push_back(a);
    }
    function<ll(int, int, int)> f = [&](int l, int r, int x){
        int ml = 0, mr = 0;
        for (int i = l; i < x; i++){
            if (a[i] > a[ml]){
                ml = i;
            }
        }
        for (int i = x + 1; i <= r; i++){
            if (a[i] > a[mr]){
                mr = i;
            }
        }
        ll out = 0;
        if (ml) out = max(out, f(l, x - 1, ml) + (x - ml));
        if (mr) out = max(out, f(x + 1, r, mr) + (mr - x));
        return out;
    };
    cout<<f(1, n, s)<<"\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26