oj.uz

Submission #306228

# Submission time Handle Problem Language Result Execution time Memory
306228 2020-09-24T23:29:03 Z CaroLinda Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 384 KB 
#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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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