oj.uz

Submission #112729

# Submission time Handle Problem Language Result Execution time Memory
112729 2019-05-21T16:14:47 Z brcode Watching (JOI13_watching) C++14
100 / 100
 298 ms 16248 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 2010;
//const int MAXP = 1e5+5;
/*

*/
vector<int> arr;
int dp[MAXN][MAXN];
int n,p,q;
bool check(int x){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j] = 1e9;
        }
    }
    dp[0][0] = 0;
    for(int i=1;i<=n;i++){
        int curr = arr[i];
        int target1 = arr[i] - x+1;

        int pos1 = lower_bound(arr.begin(),arr.end(),target1)-arr.begin()-1;
        int target2 = arr[i]-(2*x)+1;
        int pos2 = lower_bound(arr.begin(),arr.end(),target2)-arr.begin()-1;
        if(x == 14){
          //  cout<<target1<<" "<<pos2<<endl;
        }
       // 
        for(int j=0;j<=p;j++){
            if(j){
                dp[i][j] = min(dp[i][j],dp[pos1][j-1]);
            }
            dp[i][j] = min(dp[i][j],dp[pos2][j]+1);
        }
    }
    for(int i=0;i<=p;i++){
        //cout<<dp[n][i]<<endl;
        if(dp[n][i]<=q){
            return true;
        }
    }
    return false;
}
int main() {
    
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        arr.push_back(x);
    }
    if(p+q>=n){
        cout<<1<<endl;
        return 0;
    }
    arr.push_back(-1000000000);
    sort(arr.begin(),arr.end());
    int l = 0;
    int r = 1e9;
    int ans = 0;
    while(l<=r){
        int mid = (l+r)/2;
        
        if(check(mid)){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout<<ans<<endl;
}

Compilation message

watching.cpp: In function 'bool check(int)':
watching.cpp:21:13: warning: unused variable 'curr' [-Wunused-variable]
         int curr = arr[i];
             ^~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16128 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 91 ms 16128 KB Output is correct
8 Correct 109 ms 16136 KB Output is correct
9 Correct 169 ms 16248 KB Output is correct
10 Correct 298 ms 16128 KB Output is correct
11 Correct 112 ms 16120 KB Output is correct
12 Correct 202 ms 16136 KB Output is correct
13 Correct 92 ms 16124 KB Output is correct
14 Correct 89 ms 16100 KB Output is correct
15 Correct 91 ms 16128 KB Output is correct