oj.uz

Submission #283550

# Submission time Handle Problem Language Result Execution time Memory
283550 2020-08-26T00:42:50 Z wzy Watching (JOI13_watching) C++11
100 / 100
 409 ms 31864 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:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |      scanf("%lld%lld%lld" , &n , &p , &q);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:45:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |      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 1 ms 896 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 31744 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 250 ms 31864 KB Output is correct
8 Correct 271 ms 31788 KB Output is correct
9 Correct 346 ms 31744 KB Output is correct
10 Correct 409 ms 31864 KB Output is correct
11 Correct 284 ms 31792 KB Output is correct
12 Correct 366 ms 31792 KB Output is correct
13 Correct 254 ms 31864 KB Output is correct
14 Correct 253 ms 31788 KB Output is correct
15 Correct 251 ms 31864 KB Output is correct