oj.uz

Submission #59796

# Submission time Handle Problem Language Result Execution time Memory
59796 2018-07-23T06:32:30 Z gusfring Watching (JOI13_watching) C++14
100 / 100
 392 ms 16628 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3 + 5, INF = 1e8;
 
int n, p, q, a[MAXN], dp[MAXN][MAXN];

bool check(int len){
	for(int i=1, x=1, y=1; i<=n; ++i){
		while(a[i] - a[x] + 1 > len) x++;
		while(a[i] - a[y] + 1 > 2*len) y++;
		for(int j=0; j<=min(p, n); ++j) dp[i][j] = dp[y-1][j] + 1;
		for(int j=1; j<=min(p, n); ++j) dp[i][j] = min(dp[x-1][j-1], dp[i][j]);
	}
	bool ret = false;
	for(int j=0; j<=min(p, n); ++j) ret |= dp[n][j] <= q;
	return ret;
}

int main(){
	scanf("%d %d %d", &n, &p, &q);
	for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int l = 1, r = 1000000000;
	while(l < r){
		int mid = (l + r)>>1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &p, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:23:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
                          ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 3 ms 876 KB Output is correct
6 Correct 3 ms 1032 KB Output is correct
7 Correct 3 ms 1032 KB Output is correct
8 Correct 3 ms 1096 KB Output is correct
9 Correct 3 ms 1140 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 4 ms 1144 KB Output is correct
12 Correct 5 ms 1144 KB Output is correct
13 Correct 4 ms 1144 KB Output is correct
14 Correct 4 ms 1144 KB Output is correct
15 Correct 5 ms 1188 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8732 KB Output is correct
2 Correct 3 ms 8732 KB Output is correct
3 Correct 220 ms 16452 KB Output is correct
4 Correct 384 ms 16488 KB Output is correct
5 Correct 28 ms 16488 KB Output is correct
6 Correct 294 ms 16492 KB Output is correct
7 Correct 14 ms 16492 KB Output is correct
8 Correct 28 ms 16492 KB Output is correct
9 Correct 176 ms 16492 KB Output is correct
10 Correct 392 ms 16588 KB Output is correct
11 Correct 25 ms 16588 KB Output is correct
12 Correct 170 ms 16628 KB Output is correct
13 Correct 17 ms 16628 KB Output is correct
14 Correct 17 ms 16628 KB Output is correct
15 Correct 17 ms 16628 KB Output is correct