oj.uz

Submission #203568

# Submission time Handle Problem Language Result Execution time Memory
203568 2020-02-21T10:45:01 Z anonymous Mountains (IOI17_mountains) C++14
0 / 100
 5 ms 380 KB 
#include "mountains.h"
#include <vector>
#define MAXN 2005
using namespace std;
int N, dp[MAXN][MAXN];
long long H[MAXN];
bool block(int i, int j, int k) {
    //does j block view of i to k?
    if (j == k || i == j) {return(false);}
    return((H[k]-H[j])*(k-i) <(H[k]-H[i])*(k-j));
}

int slv(int l, int r) {
    if (l >= r) {return(max(r-l+1,0));}
    if (dp[l][r]) {return(dp[l][r]);}
    int peak=0, lh, rh, val=1;
    for (int i=l; i<=r; i++) {
        if (H[i] >= H[peak]) {
            peak=i;
        }
    }
    dp[l][r]=slv(l, peak-1) + slv(peak+1,r); //ignore cur
    lh = peak, rh = peak;
    for (int i=peak-1; i>=l; i--) {
        if (block(i, lh, peak)) {continue;}
        else {
            val += slv(i+1, lh-1);
            lh = i;
        }
    }
    for (int i=peak+1; i<=r; i++) {
        if (block(peak, rh, i)) {continue;}
        else {
            val += slv(rh+1, i-1);
            rh = i;
        }
    }
    dp[l][r]=max(dp[l][r], val);
    return(dp[l][r]);
}

int maximum_deevs(vector<int> y) {
	N=y.size();
	for (int i=1; i<=N; i++) {
        H[i] = y[i-1];
	}
	return(slv(1,N));
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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