oj.uz

Submission #103655

# Submission time Handle Problem Language Result Execution time Memory
103655 2019-04-01T19:31:14 Z igba Watching (JOI13_watching) C++17
50 / 100
 266 ms 32432 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int MAXN = 2020;
int n, p, q, a[MAXN], precalc[MAXN][2], dp[MAXN][MAXN];

bool ok(int w)
{
	for(int i = 1, j = 1; i <= n; ++i, j = i)
	{
		while(a[j] - a[i] < w && j <= n)
			j++;
		precalc[i][0] = j;
		while(a[j] - a[i] < 2 * w && j <= n)
			j++;
		precalc[i][1] = j;
	}
	precalc[n + 1][0] = precalc[n + 1][1] = n + 1;
	memset(dp, 0, sizeof dp);
	dp[1][0] = precalc[1][0], dp[0][1] = precalc[1][1];
	for(int i = 1; i <= p; ++i)
		for(int j = 1; j <= q; ++j)
			dp[i][j] = max(precalc[dp[i - 1][j]][0], precalc[dp[i][j - 1]][1]);
	return dp[p][q] > n;
}

signed main()
{
	scanf("%lld %lld %lld", &n, &p, &q);
	for(int i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);
	if(p + q >= n)
		printf("1\n"), exit(0);
	sort(a + 1, a + n + 1);
	int beg = 1, end = 1e9, mid;
	while(beg <= end)
	{
		mid = (beg + end) >> 1;
		if(ok(mid))
			end = mid - 1;
		else
			beg = mid + 1;
	}
	printf("%lld\n", beg);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld", &n, &p, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 32320 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 214 ms 32380 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 214 ms 32256 KB Output is correct
8 Correct 233 ms 32348 KB Output is correct
9 Correct 243 ms 32248 KB Output is correct
10 Correct 246 ms 32384 KB Output is correct
11 Correct 252 ms 32256 KB Output is correct
12 Correct 258 ms 32256 KB Output is correct
13 Correct 229 ms 32256 KB Output is correct
14 Correct 228 ms 32248 KB Output is correct
15 Correct 238 ms 32376 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 32384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 253 ms 32376 KB Output is correct
8 Correct 235 ms 32432 KB Output is correct
9 Incorrect 228 ms 32384 KB Output isn't correct
10 Halted 0 ms 0 KB -