oj.uz

Submission #124242

# Submission time Handle Problem Language Result Execution time Memory
124242 2019-07-02T21:44:35 Z tutis Mountains (IOI17_mountains) C++17
0 / 100
 2 ms 376 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
bitset<2000>ok[2000];
unordered_map<bitset<2000>, int>M;
int dp(bitset<2000> x)
{
	auto it = M.find(x);
	if (it != M.end())
		return it->second;
	int i = x._Find_first();
	if (i >= 2000)
		return 0;
	x[i] = false;
	return M[x] = max(1 + dp(x & ok[i]), dp(x));
}
int maximum_deevs(vector<int> y)
{
	assert(M.empty());
	bitset<2000>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 (j != k)
			{
				ok[i][j] = true;
			}
			else
				ok[i][j] = false;
		}
		deevs[i] = true;
	}
	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:45:2: warning: "/*" within comment [-Wcomment]
 }/**/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -