oj.uz

Submission #340706

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

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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