Submission #306220

#	Time	Username	Problem	Language	Result	Execution time	Memory
306220		Lawliet	Mountains (IOI17_mountains)	C++17	70 / 100	4 ms	1808 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 310;

struct point
{
	lli x, y;

	point(lli x = 0, lli y = 0)
		: x(x), y(y) {}

	lli operator * (point a) { return x*a.y - y*a.x; }
	point operator - (point a) { return point( x - a.x , y - a.y ); }
};

int n;

int v[MAXN];
int dp[MAXN][MAXN];

int solve(int L, int R)
{
	int& ans = dp[L][R];

	if( ans != -1 ) return ans;

	if( L > R ) return ans = 0;
	if( L == R ) return ans = 1;

	ans = 1;
	vector<point> cHull( 1 , point( L , v[L] ) );

	int last = L + 1;
	
	for(int i = L + 1 ; i <= R ; i++)
	{
		point cur( i , v[i] );

		while( (int)cHull.size() > 1 )
		{
			point A = cHull[ (int)cHull.size() - 1 ];
			point origin = cHull[ (int)cHull.size() - 2 ];

			if( (cur - origin)*(A - origin) > 0 ) break;

			cHull.pop_back();
		}

		if( (int)cHull.size() == 1 )
		{
			ans += solve( last , i - 1 );
			last = i + 1;
		}

		cHull.push_back( cur );
	}

	ans += solve( last , R );
	ans = max( ans , solve( L + 1 , R ) );

	return ans;
}

int maximum_deevs(vector<int> y) 
{
	n = (int)y.size();

	for(int i = 1 ; i <= n ; i++)
		v[i] = y[i - 1];

	memset( dp , -1 , sizeof(dp) );

	return solve( 1 , n );
}

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