Submission #340692

#	Time	Username	Problem	Language	Result	Execution time	Memory
340692		mihai145	Mountains (IOI17_mountains)	C++14	0 / 100	0 ms	364 KiB

mountains

#include "mountains.h"
#include <vector>
#define x first
#define y second

const int NMAX = 2000;

int N;
int dp[NMAX + 5][NMAX + 5];

int vf;
std::pair <int, int> st[NMAX + 5];

bool ccw(std::pair <int, int> A, std::pair <int, int> B, std::pair <int, int> C) {
    return 1LL * (B.y - A.y) * (C.x - A.x) <= 1LL * (C.y - A.y) * (B.x - A.x);
}

void Push(std::pair <int, int> dot) {
    while(vf > 1 && ccw(st[vf - 1], st[vf], dot))
        vf--;

    st[++vf] = dot;
}

int maximum_deevs(std::vector<int> y) {

    N = (int)y.size();

    for(int i = N; i >= 1; i--) {

        dp[i][i] = 1;

        vf = 0;
        Push({i - 1, y[i - 1]});

        for(int j = i + 1; j <= N; j++) {

            if(vf >= 1) {
                int t = st[vf].first + 1;
                dp[i][j] = std::max(dp[i][j], dp[i][t - 1] + dp[t + 1][j]);
            }

            if(vf > 1) {
                int s = st[vf - 1].first + 1;
                dp[i][j] = std::max(dp[i][j], dp[i][s - 1] + dp[s + 1][j]);
            }

            Push({j - 1, y[j - 1]});
        }
    }

	return dp[1][N];
}

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