제출 #340694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340694		mihai145	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	384 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 * (a.first * (b.second - c.second) + 1LL * b.first * (c.second - a.second) + 1LL * c.first * (a.second - b.second)) <= 0);
}

void Push(std::pair <int, int> dot) {
    while(vf > 1 && ccw(st[vf], st[vf - 1], 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