oj.uz

Submission #25396

# Submission time Handle Problem Language Result Execution time Memory
25396 2017-06-22T04:05:12 Z 김현수(#1065) Watching (JOI13_watching) C++11
0 / 100
 1000 ms 33440 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e9;
ll n, x[2005], a, b, dt[2005][2005];

bool can (ll P) {
	for(ll i=1;i<=n;i++) {
		for(ll j=0;j<=n;j++) {
			dt[i][j] = inf;
		}
	}
	for(ll i=1;i<=n;i++) {
		for(ll j=0,X;j<=i;j++) {
			X = lower_bound(x+1, x+1+n, x[i]+2*P) - x - 1;
			dt[X][j+1] = min(dt[i-1][j], dt[X][j+1]);
			X = lower_bound(x+1, x+1+n, x[i]+P) - x - 1;
			dt[X][j] = min(dt[i-1][j] + 1, dt[X][j]);
		}
	}
	return (dt[n][b] <= a);
}

int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	if(a + b >= n) {puts("1"); return 0;}
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&x[i]);
	}
	sort(x+1, x+1+n);
	ll S = 1, E = inf;
	while(S<E) {
		ll M = (S+E)/2;
		can(M) ? E = M : S = M+1;
	}
	printf("%lld\n",S);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:26:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&a,&b);
                                ^
watching.cpp:29:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x[i]);
                      ^

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33440 KB Output is correct
2 Correct 0 ms 33440 KB Output is correct
3 Correct 0 ms 33440 KB Output is correct
4 Correct 0 ms 33440 KB Output is correct
5 Correct 0 ms 33440 KB Output is correct
6 Correct 0 ms 33440 KB Output is correct
7 Incorrect 3 ms 33440 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 33440 KB Execution timed out
2 Halted 0 ms 0 KB -