oj.uz

Submission #74574

# Submission time Handle Problem Language Result Execution time Memory
74574 2018-09-04T04:38:41 Z wzy Watching (JOI13_watching) C++11
100 / 100
 451 ms 32440 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define int long long
int n , p , q;
int v[2002];
int dp[2002][2002];
int si[2002] , li[2002];

bool can(int mid){
	if(p+q >= n) return true;
	for(int i = 0 ; i <= n ; i++){
		for(int j = 0 ; j <= n; j ++){
			if(i == 0){
				if(j <= p) dp[i][j] = 0;
				else dp[i][j] = (int) 2e9;
			}
			else dp[i][j] = (int) 2e9;
		}
		si[i] = i , li[i] = i;
	}
	for(int i = 1 ; i <= n; i ++){
		for(int j = i ; j >= 1 ; j--){
			if(v[i] - v[j] + 1 <= mid) si[i] = j;
			if(v[i] - v[j] + 1 <= 2*mid) li[i] = j;
		}
	}
	for(int i = 1 ; i <= n; i ++){
		for(int j = 0 ; j <= min(i, p) ; j++){	
			if(j) dp[i][j] = min(dp[i][j] , dp[si[i] - 1][j-1]);
			dp[i][j] = min(dp[i][j] , dp[li[i] - 1][j] + 1);
		}
	}
	for(int j = 0 ; j <= p ; j++){
		if(dp[n][j] <= q ) return true;
	}
	return false;
}

int32_t main(){
	scanf("%lld%lld%lld" , &n , &p , &q);
	for(int i = 0 ; i < n; i ++) scanf("%lld" , &v[i+1]);
	sort(v + 1  , v + 1 + n);
	int l = 1 , r = 1000000000;
	int ansj = 1000000000;
	while(l<=r){
		int mid = (l+r)/2;
		if(can(mid)){
			ansj = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	printf("%lld\n" , ansj);
}

Compilation message

watching.cpp: In function 'int32_t main()':
watching.cpp:44: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:45:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0 ; i < n; i ++) scanf("%lld" , &v[i+1]);
                               ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 1028 KB Output is correct
8 Correct 3 ms 1028 KB Output is correct
9 Correct 3 ms 1028 KB Output is correct
10 Correct 3 ms 1028 KB Output is correct
11 Correct 3 ms 1028 KB Output is correct
12 Correct 3 ms 1028 KB Output is correct
13 Correct 3 ms 1092 KB Output is correct
14 Correct 3 ms 1112 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 32028 KB Output is correct
2 Correct 2 ms 32028 KB Output is correct
3 Correct 2 ms 32028 KB Output is correct
4 Correct 3 ms 32028 KB Output is correct
5 Correct 3 ms 32028 KB Output is correct
6 Correct 2 ms 32028 KB Output is correct
7 Correct 269 ms 32156 KB Output is correct
8 Correct 304 ms 32316 KB Output is correct
9 Correct 380 ms 32352 KB Output is correct
10 Correct 451 ms 32380 KB Output is correct
11 Correct 312 ms 32440 KB Output is correct
12 Correct 393 ms 32440 KB Output is correct
13 Correct 271 ms 32440 KB Output is correct
14 Correct 277 ms 32440 KB Output is correct
15 Correct 275 ms 32440 KB Output is correct