제출 #340707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340707		mihai145	Mountains (IOI17_mountains)	C++14	100 / 100	51 ms	14200 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--) {
        vf = 0;
        for(int j = i; j <= N; j++) {

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

            if(vf >= 1) {
                int t = st[vf].first;
                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;
                dp[i][j] = std::max(dp[i][j], dp[i][s - 1] + dp[s + 1][j]);
            }
        }
    }

	return dp[1][N];
}

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