Submission #678032

#	Time	Username	Problem	Language	Result	Execution time	Memory
678032		AngusRitossa	Mountains (IOI17_mountains)	C++14	100 / 100	126 ms	17828 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
int memo[2010][2010];
bool done[2010][2010];
vector<int> height;
int dp(int s, int e)
{
	if (s > e) return 0;
	if (done[s][e]) return memo[s][e];
	done[s][e] = true;
	int ans = 1;
	ld maxhei = -99999999999.9;
	int pre = s;
	for (int i = s+1; i <= e; i++)
	{
		ld newhei = (height[i]-height[s])/(ld)(i-s);
		if (newhei >= maxhei)
		{
			ans+=dp(pre+1, i-1);
			pre = i;
			maxhei = newhei;
		}
	}
	ans+=dp(pre+1, e);
	ans = max(ans, dp(s+1, e));
	return memo[s][e] = ans;
}
int maximum_deevs(vector<int> y) {
	int n = y.size();
	height = y;
	return dp(0, n-1);
}

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