oj.uz

Submission #747081

# Submission time Handle Problem Language Result Execution time Memory
747081 2023-05-23T15:22:15 Z Doncho_Bonboncho Mountains (IOI17_mountains) C++17
0 / 100
 1 ms 340 KB 
#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 ) - (ll)( 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 (ll)signedArea( v1, v2 );
}

bool cw( Point& a, Point& b, Point& c ){
	return ( (ll)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=0 ; 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;
	//	std::cerr<<i<<":\n";
		for( int j=i-1; 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 + 1ll + dp[j][last-1] );
	//		std::cerr<<" dp["<<j<<"]["<<i<<"] = "<<dp[j][i]<<"\n";
		}
	}

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -