제출 #340447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340447		mihai145	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	384 KiB

mountains

#include "mountains.h"
#include <vector>

const int NMAX = 2000;

int N;
int X[NMAX + 5], Y[NMAX + 5];
int dp[NMAX + 5][NMAX + 5];

struct Point {
    int x, y;
};

struct Hull {

    std::vector < Point > st;

    bool ccw(Point a, Point b, Point c) {
        return (1LL * (a.x * (b.y - c.y) + 1LL * b.x * (c.y - a.y) + 1LL * c.x * (a.y - b.y)) <= 0);
    }

    void Push(Point p) {
        while(st.size() > 1 && ccw(st[(int)st.size() - 1], st[(int)st.size() - 2], p)) {
            st.pop_back();
        }

        st.push_back(p);
    }

    int Top() {
        return st.back().x;
    }

    int Second() {
        return st[(int)st.size() - 2].x;
    }

};

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

    N = (int)y.size();

    for(int i = 0; i < N; i++) {
        X[i + 1] = i + 1;
        Y[i + 1] = y[i];
    }

    int res = 0;

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

        for(int j = i; j <= N; j++) {
            hull.Push({X[j], Y[j]});
            int top = hull.Top();

            dp[i][j] = 1;
            dp[i][j] = std::max(dp[i][j], dp[i][top - 1] + dp[top + 1][j]);

            if((int)hull.st.size() > 1) {
                int second = hull.Second();
                dp[i][j] = std::max(dp[i][j], dp[i][second - 1] + dp[second + 1][j]);
            }

            res = std::max(res, dp[i][j]);
        }
    }

	return res;
}

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