oj.uz

Submission #66044

# Submission time Handle Problem Language Result Execution time Memory
66044 2018-08-09T13:01:49 Z zadrga Watching (JOI13_watching) C++14
100 / 100
 515 ms 18464 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (int) (2 * 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 2111

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

int pos[maxn], large[maxn], small[maxn];
int dp[maxn][maxn];
int n, p, q;

int f(int x, int big){
	if(big > q)
		return INF;

	if(x == n){
		if(big <= q)
			return 0;

		return INF;
	}

	int &cur = dp[x][big];
	if(cur != -1)
		return cur;

	cur = INF;
	cur = min(cur, f(large[x], big + 1));
	cur = min(cur, f(small[x], big) + 1);
	return cur;
}

bool check(int dist){
	if(p + q >= n)
		return 1;
	
	int ind = n;
	for(int i = n - 1; i >= 0; i--){
		while(ind - 1 >= 0 && pos[ind - 1] - pos[i] >= 2 * dist)
			ind--;

		large[i] = ind;
	}

	ind = n;
	for(int i = n - 1; i >= 0; i--){
		while(ind - 1 >= 0 && pos[ind - 1] - pos[i] >= dist)
			ind--;

		small[i] = ind;
	}

	memset(dp, -1, sizeof(dp));
	if(f(0, 0) <= p)
		return 1;

	return 0;
}

int main(){
	scanf("%d%d%d", &n, &p, &q);
	for(int i = 0; i < n; i++)
		scanf("%d", pos + i);

	sort(pos, pos + n);
	pos[n] = INF;

	int l = 1, d = INF, mid, ans = -1;
	while(l <= d){
		mid = (l + d) / 2;
		if(check(mid)){
			ans = mid;
			d = mid - 1;
		}
		else 
			l = mid + 1;
	}

	printf("%d\n", ans);
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:70: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", pos + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17784 KB Output is correct
2 Correct 2 ms 17784 KB Output is correct
3 Correct 113 ms 17836 KB Output is correct
4 Correct 2 ms 17836 KB Output is correct
5 Correct 3 ms 17836 KB Output is correct
6 Correct 2 ms 17836 KB Output is correct
7 Correct 52 ms 17964 KB Output is correct
8 Correct 47 ms 17980 KB Output is correct
9 Correct 49 ms 18016 KB Output is correct
10 Correct 87 ms 18052 KB Output is correct
11 Correct 61 ms 18056 KB Output is correct
12 Correct 48 ms 18056 KB Output is correct
13 Correct 60 ms 18056 KB Output is correct
14 Correct 48 ms 18056 KB Output is correct
15 Correct 46 ms 18084 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18088 KB Output is correct
2 Correct 3 ms 18088 KB Output is correct
3 Correct 4 ms 18088 KB Output is correct
4 Correct 4 ms 18088 KB Output is correct
5 Correct 2 ms 18088 KB Output is correct
6 Correct 3 ms 18088 KB Output is correct
7 Correct 117 ms 18192 KB Output is correct
8 Correct 202 ms 18340 KB Output is correct
9 Correct 112 ms 18340 KB Output is correct
10 Correct 114 ms 18340 KB Output is correct
11 Correct 515 ms 18392 KB Output is correct
12 Correct 440 ms 18432 KB Output is correct
13 Correct 54 ms 18432 KB Output is correct
14 Correct 59 ms 18464 KB Output is correct
15 Correct 61 ms 18464 KB Output is correct