oj.uz

Submission #43791

# Submission time Handle Problem Language Result Execution time Memory
43791 2018-03-23T19:17:27 Z evpipis Watching (JOI13_watching) C++11
100 / 100
 577 ms 32028 KB 
#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

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.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16620 KB Output is correct
2 Correct 2 ms 16620 KB Output is correct
3 Correct 2 ms 16620 KB Output is correct
4 Correct 2 ms 16620 KB Output is correct
5 Correct 2 ms 16620 KB Output is correct
6 Correct 2 ms 16620 KB Output is correct
7 Correct 20 ms 16876 KB Output is correct
8 Correct 60 ms 18540 KB Output is correct
9 Correct 257 ms 28480 KB Output is correct
10 Correct 577 ms 32028 KB Output is correct
11 Correct 45 ms 32028 KB Output is correct
12 Correct 324 ms 32028 KB Output is correct
13 Correct 21 ms 32028 KB Output is correct
14 Correct 30 ms 32028 KB Output is correct
15 Correct 23 ms 32028 KB Output is correct