Submission #124269

#	Time	Username	Problem	Language	Result	Execution time	Memory
124269		tutis	Mountains (IOI17_mountains)	C++17	100 / 100	840 ms	231048 KiB

mountains

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct BitSet
{
	unsigned long long A[32];
	unsigned long long h;
	BitSet()
	{
		h = 0;
		fill_n(A, 32, 0ull);
	}
	bool operator==(const BitSet& o)const
	{
		for (int i = 0; i < 32; i++)
		{
			if (A[i] != o.A[i])
				return false;
		}
		return true;
	}
	void set(int i)
	{
		int t = i / 64;
		i %= 64;
		A[t] |= (1ull << i);
		h ^= (1ull << i);
		return;
	}
	void unset(int i)
	{
		int t = i / 64;
		i %= 64;
		A[t] &= (~(1ull << i));
		h ^= (1ull << i);
		return;
	}
	void andas(BitSet &o)
	{
		h =
		    (A[0] &= o.A[0]) ^
		    (A[1] &= o.A[1]) ^
		    (A[2] &= o.A[2]) ^
		    (A[3] &= o.A[3]) ^
		    (A[4] &= o.A[4]) ^
		    (A[5] &= o.A[5]) ^
		    (A[6] &= o.A[6]) ^
		    (A[7] &= o.A[7]) ^
		    (A[8] &= o.A[8]) ^
		    (A[9] &= o.A[9]) ^
		    (A[10] &= o.A[10]) ^
		    (A[11] &= o.A[11]) ^
		    (A[12] &= o.A[12]) ^
		    (A[13] &= o.A[13]) ^
		    (A[14] &= o.A[14]) ^
		    (A[15] &= o.A[15]) ^
		    (A[16] &= o.A[16]) ^
		    (A[17] &= o.A[17]) ^
		    (A[18] &= o.A[18]) ^
		    (A[19] &= o.A[19]) ^
		    (A[20] &= o.A[20]) ^
		    (A[21] &= o.A[21]) ^
		    (A[22] &= o.A[22]) ^
		    (A[23] &= o.A[23]) ^
		    (A[24] &= o.A[24]) ^
		    (A[25] &= o.A[25]) ^
		    (A[26] &= o.A[26]) ^
		    (A[27] &= o.A[27]) ^
		    (A[28] &= o.A[28]) ^
		    (A[29] &= o.A[29]) ^
		    (A[30] &= o.A[30]) ^
		    (A[31] &= o.A[31]);
	}
	int First(int t)
	{
		int ret = 64 * t;
		for (; t < 32; t++)
		{
			if (A[t] == 0)
			{
				ret += 64;
			}
			else
			{
				return ret + __builtin_ctzll(A[t]);
			}
		}
		return ret;
	}
};
BitSet ok[2000];
struct custom
{
	size_t operator()(const BitSet &x)const
	{
		return (x.h ^ (x.h >> 32));
	}
};
unordered_map<BitSet, int, custom>M;
int dp(BitSet x, int nuo = 0)
{
	int i = x.First(nuo / 64);
	if (i >= 2000)
		return 0;
	int &ans = M[x];
	if (ans != 0)
		return ans;
	x.unset(i);
	ans = dp(x, i + 1);
	x.andas(ok[i]);
	ans = max(ans, 1 + dp(x, i + 1));
	return ans;
}
int maximum_deevs(vector<int> y)
{
	BitSet deevs;
	for (ll i = 0; i < (ll)y.size(); i++)
	{
		ll k = i + 1;
		for (ll j = i + 1; j < (ll)y.size(); j++)
		{
			if ((y[j] - y[i]) * (k - i) >= (y[k] - y[i]) * (j - i))
				k = j;
			if (k != j)
				ok[i].set(j);
		}
		deevs.set(i);
	}
	return dp(deevs);
}/*
int main()
{
	cout << maximum_deevs({ 6, 1, 5, 2, 3, 1}) << endl;//3
	cout << maximum_deevs({ 0, 1, 2}) << endl;//1
}/**/

Compilation message (stderr)

mountains.cpp:137:2: warning: "/*" within comment [-Wcomment]
 }/**/

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