Submission #234275

#	Time	Username	Problem	Language	Result	Execution time	Memory
234275		anubhavdhar	Mountains (IOI17_mountains)	C++14	20 / 100	186 ms	384 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 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';
		}

	pair<int, int> ans = mp(-1, -1);
	F0R(mask, (1<<N))
	{
		vector<int> tmp;
		bool ok = true;
		F0R(i, N)
			if(mask&(1<<i))
				tmp.pb(i);
		for(int i : tmp)
		{
			for(int j : tmp)
			{
				if(i == j)
					continue;
				int a = min(i, j), b = max(i, j);
				if(mx(maxSlope[a][b],mp((ll)y[b] - y[a], (ll)b - a)) == mp((ll)y[b] - y[a], (ll)b - a))
				{
					// cout<<(bitset<6>(mask).to_string())<<" not ok due to indices "<<a<<" and "<<b<<'\n';
					ok = false;
					break;
				}
			}
			if(!ok)
				break;
		}
		if(ok)
			ans = max(ans, mp(__builtin_popcount(mask), mask));
	}
	// cout<<"found "<<(bitset<6>(ans.ss).to_string())<<'\n';
	return ans.ff;
}
/*
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	vector<int> y;

	
	cin>>N;
	F0R(i, N)
	{
		int j;
		cin>>j;
		y.pb(j);
	}
	cout<<maximum_deevs(y)<<' '<<maximum_deevs_brute(y);
	
	
	
	int a = 0, b = 0;
	int r = 3, cnt=0;
	while(a == b)
	{
		N = rand()%r;
		if(N == 0) N = r;
		y.clear();
		y.resize(N);
		for(int& x : y)
			x = rand()%100000;
		a = maximum_deevs(y);
		b = maximum_deevs_brute(y);
		cout<<++cnt<<'\n';
	}
	cout<<"Input : "<<N<<'\n';
	for(int x : y)
		cout<<x<<' ';
	cout<<'\n'<<a<<' '<<b;
	
	return 0;
}

 5
26924 19072 6270 5829 26777
1 2

 4
5686 6021 11662 14721
1 2
*/

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