Submission #203569

#	Time	Username	Problem	Language	Result	Execution time	Memory
203569		anonymous	Mountains (IOI17_mountains)	C++14	100 / 100	57 ms	8568 KiB

mountains

#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 (i<=j<=k)?
    if (j == k || j == i) {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;
        }
    }
    val+=slv(l, lh-1) + slv(rh+1, r);
    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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30