Submission #340689

#	Time	Username	Problem	Language	Result	Execution time	Memory
340689		mihai145	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	364 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;
 
    void Clear() {
        st.clear();
    }
 
    bool ccw(Point A, Point  B, Point C) {
        return 1LL * (B.y - A.y) * (C.x - A.x) <= 1LL * (C.y - A.y) * (B.x - A.x);
    }
 
    void Push(Point p) {
        while(st.size() > 1 && !ccw(st[(int)st.size() - 2], st[(int)st.size() - 1], 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;
        Y[i + 1] = y[i];
    }
 
    int res = 0;
 
    for(int i = N; i >= 1; i--) {
        Hull hull;
        //hull.Clear();
 
        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