제출 #124265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
124265		tutis	Mountains (IOI17_mountains)	C++17	100 / 100	870 ms	235512 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)
	{
		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 = 0;
		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];
		h = A[0] ^ A[1] ^ A[2] ^ A[3] ^ A[4] ^ A[5] ^ A[6] ^ A[7] ^
		    A[8] ^ A[9] ^ A[10] ^ A[11] ^ A[12] ^ A[13] ^ A[14] ^ A[15] ^
		    A[16] ^ A[17] ^ A[18] ^ A[19] ^ A[20] ^ A[21] ^ A[22] ^ A[23] ^
		    A[24] ^ A[25] ^ A[26] ^ A[27] ^ A[28] ^ A[29] ^ A[30] ^ 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];
map<BitSet, int>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
}/**/

컴파일 시 표준 에러 (stderr) 메시지

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

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