Submission #240040

#	Time	Username	Problem	Language	Result	Execution time	Memory
240040		nafis_shifat	Watching (JOI13_watching)	C++14	100 / 100	123 ms	15232 KiB

watching

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

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