Submission #124261

#	Time	Username	Problem	Language	Result	Execution time	Memory
124261		tutis	Mountains (IOI17_mountains)	C++17	100 / 100	857 ms	235324 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
	{
		if (h != o.h)
			return h < o.h;
		for (int i = 0; i < 32; i++)
		{
			if (A[i] != o.A[i])
				return A[i] < o.A[i];
		}
		return false;
	}
	void set(int i)
	{
		for (int t = 0; t < 32; t++)
		{
			if (i < 64)
			{
				h ^= A[t];
				A[t] |= (1ull << i);
				h ^= A[t];
				return;
			}
			else
			{
				i -= 64;
			}
		}
	}
	void unset(int i)
	{
		for (int t = 0; t < 32; t++)
		{
			if (i < 64)
			{
				h ^= A[t];
				A[t] &= (~(1ull << i));
				h ^= A[t];
				return;
			}
			else
			{
				i -= 64;
			}
		}
	}
	void andas(BitSet &o)
	{
		h = 0;
		for (int t = 0; t < 32; t++)
		{
			A[t] &= o.A[t];
			h ^= A[t];
		}
	}
	int First()
	{
		int ret = 0;
		for (int t = 0; t < 32; t++)
		{
			if (A[t] == 0)
			{
				ret += 64;
			}
			else
			{
				return ret + __builtin_ctzll(A[t]);
			}
		}
		return ret;
	}
};
BitSet ok[2000];
map<BitSet, int>M;
int dp(BitSet x)
{
	int i = x.First();
	if (i >= 2000)
		return 0;
	int &ans = M[x];
	if (ans != 0)
		return ans;
	x.unset(i);
	ans = dp(x);
	x.andas(ok[i]);
	ans = max(ans, 1 + dp(x));
	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:123:2: warning: "/*" within comment [-Wcomment]
 }/**/

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