Submission #747041

#	Time	Username	Problem	Language	Result	Execution time	Memory
747041		Doncho_Bonboncho	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	340 KiB

mountains

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

typedef long long ll;

const int MAX_N = 2048;
const int INF = 1e9;
ll dp[MAX_N][MAX_N];

struct Point{
	int x, y;
};

ll signedArea( Point& a, Point& b ){
	return (ll)( a.x + b.y ) * ( a.y - b.x );
}

ll signedArea( Point& a, Point& b, Point& c ){
	Point v1 = {b.x - a.x, b.y - a.y};
	Point v2 = {c.x - a.x, c.y - a.y};
	return signedArea( v1, v2 );
}

bool cw( Point& a, Point& b, Point& c ){
	return ( signedArea( a, b, c ) < 0ll );
}

Point p[MAX_N];

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

	int n = a.size();

	std::reverse(a.begin(), a.end());
	a.push_back(INF);
	std::reverse( a.begin(), a.end() );
	n++;

	for( int i=1 ; i<n ; i++ ){
		p[i] = {i, a[i]};
	}

	for( int i=0 ; i<n ; i++ ){
		dp[i][i] = 1ll;
		if( i ) dp[i-1][i] = 1;
		ll sum = 0;
		int last = i-1;
	//	std::cerr<<i<<":\n";
		for( int j=i-2; j>=0 ; j-- ){
	//		std::cerr<<"	-	"<<j<<"\n";
			dp[j][i] = dp[j][i-1];
			if( cw( p[i], p[last], p[j] ) ){
	//			std::cerr<<" new last \n";
				sum += dp[j+1][last-1];
	//			std::cerr<<" + "<<dp[j+1][last-1]<<"\n";
				last = j;
			}
			dp[j][i] = std::max( dp[j][i], sum + 1 );
	//		std::cerr<<" dp["<<j<<"]["<<i<<"] = "<<dp[j][i]<<"\n";
		}
	}

	return dp[0][n-1];
}

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