Submission #528942

#	Time	Username	Problem	Language	Result	Execution time	Memory
528942		tabr	Mountains (IOI17_mountains)	C++17	100 / 100	45 ms	16256 KiB

mountains

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int maximum_deevs(vector<int> y) {
    int n = (int) y.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    function<int(int, int)> solve = [&](int l, int r) {
        if (l >= r) {
            return 0;
        }
        if (dp[l][r]) {
            return dp[l][r];
        }
        int pos = (int) (max_element(y.begin() + l, y.begin() + r) - y.begin());
        dp[l][r] = 1;
        int lst = pos;
        pair<int, int> a = make_pair(1, 0);
        for (int i = pos - 1; i >= l; i--) {
            auto b = make_pair(y[pos] - y[i], pos - i);
            if (1LL * a.first * b.second >= 1LL * a.second * b.first) {
                a = b;
                dp[l][r] += solve(i + 1, lst);
                lst = i;
            }
        }
        dp[l][r] += solve(l, lst);
        lst = pos;
        a = make_pair(1, 0);
        for (int i = pos + 1; i < r; i++) {
            auto b = make_pair(y[pos] - y[i], i - pos);
            if (1LL * a.first * b.second >= 1LL * a.second * b.first) {
                a = b;
                dp[l][r] += solve(lst + 1, i);
                lst = i;
            }
        }
        dp[l][r] += solve(lst + 1, r);
        dp[l][r] = max(dp[l][r], solve(l, pos) + solve(pos + 1, r));
        return dp[l][r];
    };
    return solve(0, n);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    debug(maximum_deevs({6, 1, 5, 2, 3, 1}));
    debug(maximum_deevs({0, 1, 2}));
    return 0;
}
#endif

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30