oj.uz

Submission #59140

# Submission time Handle Problem Language Result Execution time Memory
59140 2018-07-20T17:09:41 Z RezwanArefin01 Watching (JOI13_watching) C++17
100 / 100
 729 ms 16876 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 2010; 
int n, p, q, a[N], dp[N][N], w;
int np[N], nq[N]; 

int f(int i, int t) {
	if(t > p) return 1e9; 
	if(i == n) return 0; 
	int &ret = dp[i][t]; 
	if(~ret) return ret;
	return ret = min(f(np[i], t + 1), 1 + f(nq[i], t)); 
}
bool check(int w) {
	int j = 0, k = 0; 
	for(int i = 0; i < n; i++) {
		while(j < n && a[i] + w > a[j]) j++; 
		while(k < n && a[i] + w + w > a[k]) k++; 
		np[i] = j; nq[i] = k; 
	}
	memset(dp, -1, sizeof dp); 
	return f(0, 0) <= q; 
}
int main(int argc, char const *argv[]) {
	scanf("%d %d %d", &n, &p, &q); 
	for(int i = 0; i < n; i++) 
		scanf("%d", &a[i]); 
	p = min(p, n); 
	sort(a, a + n);
	int lo = 1, hi = 1e9, ans = -1; 
	while(lo <= hi) {
		int mid = lo + hi >> 1; 
		if(check(mid)) {
			ans = mid, hi = mid - 1; 
		} else lo = mid + 1; 
	} printf("%d\n", ans);
}

Compilation message

watching.cpp: In function 'int main(int, const char**)':
watching.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1; 
             ~~~^~~~
watching.cpp:29: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:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]); 
   ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 16164 KB Output is correct
2 Correct 135 ms 16356 KB Output is correct
3 Correct 124 ms 16356 KB Output is correct
4 Correct 76 ms 16356 KB Output is correct
5 Correct 106 ms 16388 KB Output is correct
6 Correct 137 ms 16392 KB Output is correct
7 Correct 133 ms 16460 KB Output is correct
8 Correct 133 ms 16460 KB Output is correct
9 Correct 74 ms 16548 KB Output is correct
10 Correct 129 ms 16548 KB Output is correct
11 Correct 133 ms 16548 KB Output is correct
12 Correct 131 ms 16548 KB Output is correct
13 Correct 128 ms 16548 KB Output is correct
14 Correct 129 ms 16572 KB Output is correct
15 Correct 128 ms 16572 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 16572 KB Output is correct
2 Correct 54 ms 16572 KB Output is correct
3 Correct 453 ms 16756 KB Output is correct
4 Correct 593 ms 16756 KB Output is correct
5 Correct 108 ms 16756 KB Output is correct
6 Correct 596 ms 16764 KB Output is correct
7 Correct 136 ms 16764 KB Output is correct
8 Correct 157 ms 16764 KB Output is correct
9 Correct 307 ms 16764 KB Output is correct
10 Correct 729 ms 16764 KB Output is correct
11 Correct 179 ms 16764 KB Output is correct
12 Correct 412 ms 16876 KB Output is correct
13 Correct 55 ms 16876 KB Output is correct
14 Correct 70 ms 16876 KB Output is correct
15 Correct 49 ms 16876 KB Output is correct