Submission #43791

#	Time	Username	Problem	Language	Result	Execution time	Memory
43791		evpipis	Watching (JOI13_watching)	C++11	100 / 100	577 ms	32028 KiB

watching

#include <bits/stdc++.h>
using namespace std;

const int len = 2e3+5, inf = 1e9;
int n, p, q, a[len];
int nex[2][len], pre[2][len], dp[len][len], best[len][len];

/*int finduse(int pos, int use1){
    if (pos == 0 && use1 == 0) return 0;
    if (pos == 0 && use1 != 0) return inf;
    if (best[pos][use1] != -1) return best[pos][use1];

    int ans = inf;
    if (use1 > 0)
        ans = min(ans, finduse(pre[0][pos], use1-1));
    ans = min(ans, finduse(pre[1][pos], use1)+1);

    return best[pos][use1] = ans;
}

int solve(int pos, int use1){
    if (pos == n+1) return 1;
    if (dp[pos][use1] != -1) return dp[pos][use1];

    int use2 = finduse(pos-1, use1), ans = 0;
    if (use1 < pp)
        ans = max(ans, solve(nex[0][pos], use1+1));
    if (use2 < qq)
        ans = max(ans, solve(nex[1][pos], use1));

    //if (hey) printf("pos = %d, use1 = %d, use2 = %d, ans = %d\n", pos, use1, use2, ans);
    return dp[pos][use1] = ans;
}*/

bool check(int w){
    for (int i = 1, j1 = 1, j2 = 1; i <= n; i++){
        while (j1 <= n && a[j1]-a[i]+1 <= w) j1++;
        while (j2 <= n && a[j2]-a[i]+1 <= 2*w) j2++;

        nex[0][i] = j1;
        nex[1][i] = j2;
    }

    for (int i = n, j1 = n, j2 = n; i >= 1; i--){
        while (j1 >= 1 && a[i]-a[j1]+1 <= w) j1--;
        while (j2 >= 1 && a[i]-a[j2]+1 <= 2*w) j2--;

        pre[0][i] = j1;
        pre[1][i] = j2;
    }

    /*qq = q, pp = p;
    if (q < p){
        swap(pp, qq);
        for (int i = 1; i <= n; i++){
            swap(nex[0][i], nex[1][i]);
            swap(pre[0][i], pre[1][i]);
        }
    }*/

    for (int i = 1; i <= p; i++)
        best[0][i] = inf;
    best[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= p; j++){
            best[i][j] = min(inf, best[pre[1][i]][j]+1);
            if (j > 0) best[i][j] = min(best[i][j], best[pre[0][i]][j-1]);
        }

    for (int i = 0; i <= p; i++)
        dp[n+1][i] = 1;
    for (int i = n; i >= 1; i--)
        for (int j1 = 0; j1 <= p; j1++){
            int j2 = best[i-1][j1];
            dp[i][j1] = 0;
            if (j1 < p) dp[i][j1] = (dp[i][j1] | dp[nex[0][i]][j1+1]);
            if (j2 < q) dp[i][j1] = (dp[i][j1] | dp[nex[1][i]][j1]);
        }

    return dp[1][0];
}

int bs(){
    int l = 1, r = inf/2, ans;
    while (l <= r){
        int mid = (l+r)/2;
        if (check(mid)){
            ans = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }

    return ans;
}

void read(int &res){
    char c;
    while (c = getchar(), c < '0' || c > '9'){}
    res = c-'0';
    while (c = getchar(), c >= '0' && c <= '9')
        res = 10*res+c-'0';
}

int main(){
    read(n), read(p), read(q);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    sort(a+1, a+n+1);

    if (p+q >= n) printf("1\n");
    else printf("%d\n", bs());
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int bs()':
watching.cpp:95:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^

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