oj.uz

답안 #340689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340689 2020-12-28T07:51:17 Z mihai145 Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 364 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;
 
    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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 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 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 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 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 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 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 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 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -