Submission #411704

#	Time	Username	Problem	Language	Result	Execution time	Memory
411704		nxteru	Mountains (IOI17_mountains)	C++14	100 / 100	30 ms	16152 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int>y;
int dp[2005][2005];
int solve(int l,int r){
	if(r<l)return 0;
	if(l==r)return 1;
	if(dp[l][r]!=-1)return dp[l][r];
	int ma=-1;
	for(int i=l;i<=r;i++){
		if(ma==-1||y[ma]<y[i])ma=i;
	}
	int s=1;
	int la=ma;
	for(int i=ma-1;i>=l;i--){
		if(ll(y[ma]-y[i])*ll(ma-la)<=ll(y[ma]-y[la])*ll(ma-i)){
			s+=solve(i+1,la-1);
			la=i;
		}
	}
	s+=solve(l,la-1);
	la=ma;
	for(int i=ma+1;i<=r;i++){
		if(ll(y[ma]-y[i])*ll(ma-la)>=ll(y[ma]-y[la])*ll(ma-i)){
			s+=solve(la+1,i-1);
			la=i;
		}
	}
	s+=solve(la+1,r);
	return dp[l][r]=max(s,solve(l,ma-1)+solve(ma+1,r));
}
int maximum_deevs(vector<int> Y) {
	y=Y;
	int n=y.size();
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)dp[i][j]=-1;
	return solve(0,y.size()-1);
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30