Submission #81590

#	Time	Username	Problem	Language	Result	Execution time	Memory
81590		chelly	Watching (JOI13_watching)	C++11	100 / 100	645 ms	1032 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int dp[2][MAXN], N, P, Q;
vector<int> events;
int next (int i, int w){
    if (i>=N) return N;
    int lo = i, hi = N;
    while (lo<hi){
        int mid = (lo+hi+1)/2;
        if (events[mid-1]-events[i-1]+1<=w) lo = mid;
        else hi = mid-1;
    }
    return lo;
}
bool check (int w){
    memset (dp, 0, sizeof dp);
    for (int i = 0; i<=P; i++){
        for (int j = 0; j<=Q; j++){
            if (i>0) dp[i%2][j] = max(dp[i%2][j], next(dp[(i-1)%2][j]+1, w));
            if (j>0) dp[i%2][j] = max(dp[i%2][j], next(dp[i%2][j-1]+1, 2*w));
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            if (dp[i%2][j]==N) return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d", &N, &P, &Q);
    P = min(N, P);
    Q = min(N, Q);
    for (int i = 0, a; i<N; i++){
        scanf("%d", &a);
        events.push_back(a);
    }
    sort (events.begin(), events.end());
    int lo = 1, hi = 1000000000;
    while (lo<hi){
        int mid = (lo+hi)/2;
        //cout<<lo<<" "<<hi<<" "<<mid<<endl;
        if (check(mid)) hi = mid;
        else lo = mid+1;
    }
    printf("%d\n", lo);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &P, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50