oj.uz

Submission #124274

# Submission time Handle Problem Language Result Execution time Memory
124274 2019-07-02T22:56:38 Z tutis Mountains (IOI17_mountains) C++17
20 / 100
 4 ms 2036 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
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));
	}
};
gp_hash_table<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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 2 ms 888 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 3 ms 888 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 2 ms 888 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 3 ms 888 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 2 ms 1016 KB Output is correct
19 Correct 2 ms 1016 KB Output is correct
20 Correct 3 ms 1016 KB Output is correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 2 ms 1016 KB Output is correct
24 Correct 2 ms 1016 KB Output is correct
25 Correct 2 ms 1016 KB Output is correct
26 Correct 2 ms 1016 KB Output is correct
27 Correct 2 ms 1016 KB Output is correct
28 Correct 3 ms 1144 KB Output is correct
29 Correct 2 ms 1148 KB Output is correct
30 Correct 2 ms 1144 KB Output is correct
31 Correct 3 ms 1148 KB Output is correct
32 Runtime error 4 ms 2036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 2 ms 888 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 3 ms 888 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 2 ms 1016 KB Output is correct
19 Correct 2 ms 1016 KB Output is correct
20 Correct 3 ms 1016 KB Output is correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 2 ms 1016 KB Output is correct
24 Correct 2 ms 1016 KB Output is correct
25 Correct 2 ms 1016 KB Output is correct
26 Correct 2 ms 1016 KB Output is correct
27 Correct 2 ms 1016 KB Output is correct
28 Correct 3 ms 1144 KB Output is correct
29 Correct 2 ms 1148 KB Output is correct
30 Correct 2 ms 1144 KB Output is correct
31 Correct 3 ms 1148 KB Output is correct
32 Runtime error 4 ms 2036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 2 ms 888 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 3 ms 888 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 2 ms 1016 KB Output is correct
19 Correct 2 ms 1016 KB Output is correct
20 Correct 3 ms 1016 KB Output is correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 2 ms 1016 KB Output is correct
24 Correct 2 ms 1016 KB Output is correct
25 Correct 2 ms 1016 KB Output is correct
26 Correct 2 ms 1016 KB Output is correct
27 Correct 2 ms 1016 KB Output is correct
28 Correct 3 ms 1144 KB Output is correct
29 Correct 2 ms 1148 KB Output is correct
30 Correct 2 ms 1144 KB Output is correct
31 Correct 3 ms 1148 KB Output is correct
32 Runtime error 4 ms 2036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -