Submission #237302

#	Time	Username	Problem	Language	Result	Execution time	Memory
237302		Mamedov	Watching (JOI13_watching)	C++14	100 / 100	291 ms	8696 KiB

watching

#include <bits/stdc++.h>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back

using namespace std;

const int MAX = 2002;
int n, p, q;
int dp[MAX][MAX];
int x[MAX];

int Find(int pos, int seg) {
    int xpos = x[pos + 1] + seg - 1;
    int l = pos + 1, r = n - 1, mid;
    int last = pos;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(x[mid] <= xpos) {
            l = mid + 1;
            last = mid;
        }else {
            r = mid - 1;
        }
    }
    return last;
}
bool check(int w) {
    dp[0][0] = -1;
    for(int i = 0; i <= p; ++i) {
        for(int j = 0; j <= q; ++j) {
            if(i == 0 && j == 0) continue;
            if(j == 0) dp[i][j] = Find(dp[i - 1][j], w);
            else if(i == 0) dp[i][j] = Find(dp[i][j - 1], w + w);
            else dp[i][j] = max(Find(dp[i - 1][j], w), Find(dp[i][j - 1], w + w));
            if(dp[i][j] == n - 1) return true;
        }
    }
    return false;
}
int solve(){
    ios_base::sync_with_stdio(false);
    cin >> n >> p >> q;
    for(int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    sort(x, x + n);
    if(p + q >= n) return 1;
    int l = 1, r = x[n - 1];
    int mid, w;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(check(mid)) {
            w = mid;
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    return w;
}
int main()
{
    cout << solve() << '\n';
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int solve()':
watching.cpp:51:14: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int mid, w;
              ^

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