Submission #283550

#	Time	Username	Problem	Language	Result	Execution time	Memory
283550		wzy	Watching (JOI13_watching)	C++11	100 / 100	409 ms	31864 KiB

watching

    #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 (stderr)

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 / 50
• Subtask 2: 50 / 50