oj.uz

Submission #124257

# Submission time Handle Problem Language Result Execution time Memory
124257 2019-07-02T22:24:09 Z tutis Mountains (IOI17_mountains) C++17
20 / 100
 278 ms 262144 KB 
#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];
	BitSet()
	{
		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 A[i] < o.A[i];
		}
		return false;
	}
	void set(int i)
	{
		for (int t = 0; t < 32; t++)
		{
			if (i < 64)
			{
				A[t] |= (1ull << i);
				return;
			}
			else
			{
				i -= 64;
			}
		}
	}
	void unset(int i)
	{
		for (int t = 0; t < 32; t++)
		{
			if (i < 64)
			{
				A[t] &= (~(1ull << i));
				return;
			}
			else
			{
				i -= 64;
			}
		}
	}
	void andas(BitSet &o)
	{
		for (int t = 0; t < 32; t++)
			A[t] &= o.A[t];
	}
	int First()
	{
		int ret = 0;
		for (int t = 0; t < 32; t++)
		{
			if (A[t] == 0)
			{
				ret += 64;
			}
			else
			{
				return ret + __builtin_ctz(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

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

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 756 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Runtime error 278 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 756 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Runtime error 278 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 756 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Runtime error 278 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -