oj.uz

Submission #124252

# Submission time Handle Problem Language Result Execution time Memory
124252 2019-07-02T22:05:25 Z tutis Mountains (IOI17_mountains) C++17
0 / 100
 2 ms 376 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;
int maximum_deevs(vector<int> y)
{
	int n = y.size();
	int k[n][n];
	for (ll i = 0; i < n; i++)
	{
		k[i][i] = i + 1;
		for (ll j = i + 1; j < n; j++)
		{
			if ((y[j] - y[i]) * (k[i][j - 1] - i) >=
			        (y[k[i][j - 1]] - y[i]) * (j - i))
				k[i][j] = j;
			else
				k[i][j] = k[i][j - 1];
		}
	}
	int ret = 1;
	int dp[n][n];
	for (int sz = 1; sz <= n; sz++)
	{
		for (int i = 0; i + sz - 1 < n; i++)
		{
			int j = i + sz - 1;
			if (i == j)
				dp[i][j] = 1;
			else
			{
				if (k[i][j] != j)
					ret = max(ret, dp[i][j] = dp[i][k[i][j] - 1] + dp[k[i][j] + 1][j]);
				else
					dp[i][j] = -3000;
			}
		}
	}
	return ret;
}/*
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:48: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 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 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 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 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 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 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 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -