Submission #306221

#	Time	Username	Problem	Language	Result	Execution time	Memory
306221		Lawliet	Mountains (IOI17_mountains)	C++17	100 / 100	39 ms	14328 KiB

mountains

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

using namespace std;
typedef long long int lli;

const int MAXN = 2010;

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 maximum_deevs(vector<int> y) 
{
	n = (int)y.size();

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

	for(int L = n ; L > 0 ; L--)
	{
		dp[L][L] = 1;

		int sum = 0;
		int last = L + 1;
		vector<point> cHull( 1 , point( L , v[L] ) );

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

			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 )
			{
				sum += dp[last][R - 1];
				last = R + 1;
			}

			cHull.push_back( cur );
			dp[L][R] = max( dp[L][R] , sum + 1 + dp[last][R] );
		}
	}

	return dp[1][n];
}

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