oj.uz

Submission #63505

# Submission time Handle Problem Language Result Execution time Memory
63505 2018-08-02T04:35:41 Z njchung99 Watching (JOI13_watching) C++14
100 / 100
 236 ms 9028 KB 
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll x[2050];
int dp[2010][2010];
int nex[2010][2];
int main()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	if (m + k >= n)
	{
		puts("1");
		return 0;
	}
	for (int i = 0; i < n; i++)
		scanf("%lld", &x[i]);
	sort(x, x + n);
	unique(x, x + n) - x;
	ll left = 1;
	ll right = 9999999999;
	ll dap = 1e15;
	while (left <= right)
	{
		ll mid = (left + right) / 2;
		nex[n][0] = n-1;
		nex[n][1] = n-1;
		for (int i = 0; i < n; i++)
		{
			nex[i][0] = lower_bound(x, x + n, x[i] + mid) - x-1;
			nex[i][1] = lower_bound(x, x + n, 2 * mid + x[i]) - x-1;
		}
		for (int i = 0; i <= m; i++)
		{
			for (int y = 0; y <= k; y++)
			{
				dp[i][y] = -1;
				if (i)dp[i][y] = max(dp[i][y], nex[dp[i - 1][y] + 1][0]);
				if (y)dp[i][y] = max(dp[i][y], nex[dp[i][y - 1] + 1][1]);
			}
		}
		if (dp[m][k] >= n - 1)
		{
			right = mid - 1;
			dap = min(dap, mid);
		}
		else {
			left = mid + 1;
		}
	}
	printf("%lld\n", dap);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:20:19: warning: value computed is not used [-Wunused-value]
  unique(x, x + n) - x;
  ~~~~~~~~~~~~~~~~~^~~
watching.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 3 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 4 ms 572 KB Output is correct
9 Correct 3 ms 572 KB Output is correct
10 Correct 3 ms 660 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 4 ms 748 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 3 ms 748 KB Output is correct
15 Correct 4 ms 748 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 8 ms 748 KB Output is correct
8 Correct 30 ms 1516 KB Output is correct
9 Correct 32 ms 3980 KB Output is correct
10 Correct 55 ms 9028 KB Output is correct
11 Correct 45 ms 9028 KB Output is correct
12 Correct 236 ms 9028 KB Output is correct
13 Correct 10 ms 9028 KB Output is correct
14 Correct 11 ms 9028 KB Output is correct
15 Correct 10 ms 9028 KB Output is correct