oj.uz

Submission #340693

# Submission time Handle Problem Language Result Execution time Memory
340693 2020-12-28T08:14:35 Z mihai145 Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 384 KB 
#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 - 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--) {

        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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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