oj.uz

Submission #553655

# Submission time Handle Problem Language Result Execution time Memory
553655 2022-04-26T13:07:06 Z QwertyPi Watching (JOI13_watching) C++14
100 / 100
 317 ms 16204 KB 
#include <bits/stdc++.h>
#define N 2013
using namespace std;
 
int dp[N][N];
int W1[N], W2[N];
int n, p, q;
vector<int> a;
 
bool ok(int w){
	for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) dp[i][j] = (1 << 30); dp[0][0] = 0;
	int w1 = 0, w2 = 0;
	for(int i = 1; i <= n; i++){
		while(w2 < n && a[w2] <= a[i - 1] - w * 2) w2++;
		while(w1 < n && a[w1] <= a[i - 1] - w) w1++;
		W1[i] = w1, W2[i] = w2;
	}
	for(int j = 0; j <= q; j++){
		for(int i = 1; i <= n; i++){
			if(j > 0) dp[j][i] = min(dp[j][i], dp[j - 1][W2[i]]);
			dp[j][i] = min(dp[j][i], dp[j][W1[i]] + 1);
		}
		for(int i = 1; i <= n; i++) dp[j + 1][i] = min(dp[j][i], dp[j + 1][i]);
	}
	return dp[q][n] <= p;
}
 
int main(){
	cin >> n >> p >> q;
	p += q - min(n / 2, q);
	p = min(n, p); q = min(n / 2, q);
	for(int i = 0; i < n; i++){
		int v; cin >> v;
		a.push_back(v);
	}
	sort(a.begin(), a.end());
	int l, r;
	for(l = 0, r = 1e9 + 1; l != r;){
		int m = (l + r) / 2;
		if(ok(m)){
			r = m;
		}else{
			l = m + 1;
		}
	}
	cout << l << endl;
}

Compilation message

watching.cpp: In function 'bool ok(int)':
watching.cpp:11:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   11 |  for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) dp[i][j] = (1 << 30); dp[0][0] = 0;
      |  ^~~
watching.cpp:11:80: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   11 |  for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) dp[i][j] = (1 << 30); dp[0][0] = 0;
      |                                                                                ^~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 684 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 696 KB Output is correct
9 Correct 1 ms 696 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 692 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 16084 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 317 ms 16092 KB Output is correct
4 Correct 91 ms 16096 KB Output is correct
5 Correct 306 ms 16096 KB Output is correct
6 Correct 307 ms 16096 KB Output is correct
7 Correct 75 ms 16080 KB Output is correct
8 Correct 225 ms 16120 KB Output is correct
9 Correct 102 ms 16100 KB Output is correct
10 Correct 95 ms 16084 KB Output is correct
11 Correct 298 ms 16108 KB Output is correct
12 Correct 305 ms 16132 KB Output is correct
13 Correct 78 ms 16096 KB Output is correct
14 Correct 76 ms 16204 KB Output is correct
15 Correct 81 ms 16100 KB Output is correct