oj.uz

Submission #340447

# Submission time Handle Problem Language Result Execution time Memory
340447 2020-12-27T15:58:53 Z mihai145 Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -