oj.uz

Submission #68372

# Submission time Handle Problem Language Result Execution time Memory
68372 2018-08-16T21:36:19 Z Kerim Watching (JOI13_watching) C++17
100 / 100
 539 ms 16928 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,X,Y;
int arr[MAXN],a[MAXN],b[MAXN];
const int N=2004;
int dp[N][N];
int rec(int x,int y){
	if(x>n)
		return 0;
	int &ret=dp[x][y];
	if(~ret)
		return ret;
	ret=rec(b[x],y)+1;
	if(y)
		umin(ret,rec(a[x],y-1));
	return ret;	
}
bool ok(int w){
	int p=n;
	for(int i=n;i>=1;i--){
		while(arr[p]-arr[i]>=w)
			p--;
		a[i]=p+1;	
	}p=n;
	for(int i=n;i>=1;i--){
		while(arr[p]-arr[i]>=2*w)
			p--;
		b[i]=p+1;	
	}	
	memset(dp,-1,sizeof dp);
	return (rec(1,min(n,X))<=Y);
}
int main(){
    //~ freopen("file.in", "r", stdin); 
    scanf("%d%d%d",&n,&X,&Y);
    for(int i=1;i<=n;i++)
		scanf("%d",arr+i);
	sort(arr+1,arr+n+1);
	int st=1,en=INF;
	while(st+1<en){
		int mid=(st+en)>>1;
		if(ok(mid))
			en=mid;
		else
			st=mid;
	}
	if(ok(st))
		en=st;
	printf("%d\n",en);	
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&X,&Y);
     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",arr+i);
   ~~~~~^~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16120 KB Output is correct
2 Correct 50 ms 16120 KB Output is correct
3 Correct 52 ms 16168 KB Output is correct
4 Correct 61 ms 16376 KB Output is correct
5 Correct 41 ms 16376 KB Output is correct
6 Correct 45 ms 16376 KB Output is correct
7 Correct 54 ms 16376 KB Output is correct
8 Correct 49 ms 16376 KB Output is correct
9 Correct 52 ms 16376 KB Output is correct
10 Correct 44 ms 16376 KB Output is correct
11 Correct 56 ms 16380 KB Output is correct
12 Correct 49 ms 16380 KB Output is correct
13 Correct 55 ms 16380 KB Output is correct
14 Correct 56 ms 16408 KB Output is correct
15 Correct 118 ms 16412 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16436 KB Output is correct
2 Correct 42 ms 16436 KB Output is correct
3 Correct 384 ms 16580 KB Output is correct
4 Correct 412 ms 16648 KB Output is correct
5 Correct 74 ms 16648 KB Output is correct
6 Correct 445 ms 16760 KB Output is correct
7 Correct 49 ms 16776 KB Output is correct
8 Correct 166 ms 16776 KB Output is correct
9 Correct 198 ms 16776 KB Output is correct
10 Correct 539 ms 16852 KB Output is correct
11 Correct 162 ms 16852 KB Output is correct
12 Correct 435 ms 16928 KB Output is correct
13 Correct 112 ms 16928 KB Output is correct
14 Correct 93 ms 16928 KB Output is correct
15 Correct 47 ms 16928 KB Output is correct