Submission #234132

#	Time	Username	Problem	Language	Result	Execution time	Memory
234132		anubhavdhar	Mountains (IOI17_mountains)	C++14	0 / 100	5 ms	512 KiB

mountains

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30