oj.uz

Submission #234132

# Submission time Handle Problem Language Result Execution time Memory
234132 2020-05-23T09:29:23 Z anubhavdhar Mountains (IOI17_mountains) C++14
0 / 100
 5 ms 512 KB 
#include<bits/stdc++.h>
#include "mountains.h"
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()

using namespace std;
/*
const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/

#define INF 100000000000000000

inline bool xr(bool a, bool b)
{
	return ((a && (!b)) || (b && (!a)));
}

ii mx(ii slope1, ii slope2)
{
	return ((xr( slope1.ff * slope2.ss > slope2.ff * slope1.ss , slope1.ss * slope2.ss < 0)) ? slope1 : slope2);
}

int maximum_deevs(vector<int> y)
{
	int N = y.size();
	pair<int, int> A[N];
	ii maxSlope[N][N];
	F0R(i, N)
		F0R(j, N)
			maxSlope[i][j] = mp(-INF,1);
	F0R(i, N)
		F0Rr(j, i+1, N)
		{
			maxSlope[i][j] = mx(maxSlope[i][j-1], mp(y[j] - y[i], j - i));
			// cout<<"maxSlope["<<i<<"]["<<j<<"] = "<<maxSlope[i][j].ff<<'/'<<maxSlope[i][j].ss<<'\n';
		}
	F0R(i, N)
		A[i] = mp(y[i], i);
	sort(A, A + N);
	vector<int> Answer;
	F0R(i, N)
	{
		bool ok = true;
		// cout<<A[i].ff<<","<<A[i].ss<<'\n';
		for(int j : Answer)
		{
			int a = min(A[i].ss, j), b = max(A[i].ss, j);
			if(mx(maxSlope[a][b],mp((ll)y[b] - y[a], (ll)b - a)) == mp((ll)y[b] - y[a], (ll)b - a))
			{
				ok = false;
				break;
			}
		}
		if(ok)
			Answer.pb(A[i].ss);
		// else
			// cout<<"no\n";
	}
	// cout<<Answer.size()<<'\n';
	// for(int i : Answer)
		// cout<<y[i]<<' '<<i<<'\n';
	return Answer.size();
}
/*
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin>>N;
	vector<int> y(N);
	for(int& x : y)
		cin>>x;
	cout<<maximum_deevs(y);
	return 0;
}*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Incorrect 4 ms 256 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Incorrect 4 ms 256 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Incorrect 4 ms 256 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Incorrect 4 ms 256 KB Output isn't correct
16 Halted 0 ms 0 KB -