Submission #306228

#	Time	Username	Problem	Language	Result	Execution time	Memory
306228		CaroLinda	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	384 KiB

mountains

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

#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define ll long long

using namespace std ;

struct Fraq
{
	ll num , den ;
	Fraq(ll num = 0 , ll den = 1 ) : num(num), den(den) {}
	bool operator < (Fraq other) const { return num * other.den < den * other.num ; }
	bool operator == (Fraq other) const { return num * other.den == den * other.num ; }
	bool operator > (Fraq other) const { return num * other.den > den * other.num ; }
} ;

int maximum_deevs(std::vector<int> y) {

	int n = sz(y) ;
	vector<int> dp(n,1) ;

	for(int i = n-1 ; i >= 0 ; i-- )
	{
		set<Fraq> s ;

		for(int j = i + 1 ; j < n ; j++ )
		{

			Fraq slope = Fraq( y[j] - y[i] , j - i ) ;
			
			if(s.upper_bound(slope) != s.end() ) dp[i] = max(dp[i] , dp[j] + 1 ) ;

			s.insert(Fraq(y[j], j) ) ;

		}

	}

	return *max_element(all(dp) ) ;

}

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