oj.uz

Submission #240040

# Submission time Handle Problem Language Result Execution time Memory
240040 2020-06-17T19:57:25 Z nafis_shifat Watching (JOI13_watching) C++14
100 / 100
 123 ms 15232 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2001;
int p,q,n;
int a[mxn];
bool check(int w) {
    int dp[n+1][p+1];
    for(int i=0;i<=p;i++)dp[0][i]=0;
    int cur=1;
    int pt1=1,pt2=1;
    for(int i=1;i<=n;i++) {
        while(a[i]-a[pt1]>=w)pt1++;
        while(a[i]-a[pt2]>=2*w)pt2++;
        dp[i][0]=dp[pt2-1][0]+1;
        for(int j=1;j<=p;j++) {
            dp[i][j]=min(dp[pt1-1][j-1],dp[pt2-1][j]+1);
        }
    }
    
    return dp[n][p]<=q;
}
int main() {
    cin>>n>>p>>q;
    if(p+q>=n) {
        cout<<1<<endl;
        return 0;
    }
    
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int lo=1;
    int hi=1e9;
    int ans;
    while(lo<=hi) {
        int mid=lo+hi>>1;
        if(check(mid)) {
            ans=mid;
            hi=mid-1;
        } else {
            lo=mid+1;
        }
    }
    cout<<ans<<endl;
}

Compilation message

watching.cpp: In function 'bool check(int)':
watching.cpp:10:9: warning: unused variable 'cur' [-Wunused-variable]
     int cur=1;
         ^~~
watching.cpp: In function 'int main()':
watching.cpp:36:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lo+hi>>1;
                 ~~^~~
watching.cpp:44:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<ans<<endl;
           ^~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 424 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 15 ms 1280 KB Output is correct
9 Correct 53 ms 6272 KB Output is correct
10 Correct 123 ms 15232 KB Output is correct
11 Correct 16 ms 1024 KB Output is correct
12 Correct 70 ms 8064 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 9 ms 512 KB Output is correct
15 Correct 7 ms 512 KB Output is correct