oj.uz

Submission #234275

# Submission time Handle Problem Language Result Execution time Memory
234275 2020-05-23T17:27:10 Z anubhavdhar Mountains (IOI17_mountains) C++14
20 / 100
 186 ms 384 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 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 175 ms 376 KB Output is correct
7 Correct 169 ms 376 KB Output is correct
8 Correct 170 ms 256 KB Output is correct
9 Correct 177 ms 256 KB Output is correct
10 Correct 87 ms 256 KB Output is correct
11 Correct 186 ms 368 KB Output is correct
12 Correct 168 ms 256 KB Output is correct
13 Correct 171 ms 256 KB Output is correct
14 Correct 179 ms 256 KB Output is correct
15 Correct 170 ms 376 KB Output is correct
16 Correct 169 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 175 ms 376 KB Output is correct
7 Correct 169 ms 376 KB Output is correct
8 Correct 170 ms 256 KB Output is correct
9 Correct 177 ms 256 KB Output is correct
10 Correct 87 ms 256 KB Output is correct
11 Correct 186 ms 368 KB Output is correct
12 Correct 168 ms 256 KB Output is correct
13 Correct 171 ms 256 KB Output is correct
14 Correct 179 ms 256 KB Output is correct
15 Correct 170 ms 376 KB Output is correct
16 Correct 169 ms 376 KB Output is correct
17 Incorrect 5 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 175 ms 376 KB Output is correct
7 Correct 169 ms 376 KB Output is correct
8 Correct 170 ms 256 KB Output is correct
9 Correct 177 ms 256 KB Output is correct
10 Correct 87 ms 256 KB Output is correct
11 Correct 186 ms 368 KB Output is correct
12 Correct 168 ms 256 KB Output is correct
13 Correct 171 ms 256 KB Output is correct
14 Correct 179 ms 256 KB Output is correct
15 Correct 170 ms 376 KB Output is correct
16 Correct 169 ms 376 KB Output is correct
17 Incorrect 5 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 175 ms 376 KB Output is correct
7 Correct 169 ms 376 KB Output is correct
8 Correct 170 ms 256 KB Output is correct
9 Correct 177 ms 256 KB Output is correct
10 Correct 87 ms 256 KB Output is correct
11 Correct 186 ms 368 KB Output is correct
12 Correct 168 ms 256 KB Output is correct
13 Correct 171 ms 256 KB Output is correct
14 Correct 179 ms 256 KB Output is correct
15 Correct 170 ms 376 KB Output is correct
16 Correct 169 ms 376 KB Output is correct
17 Incorrect 5 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -