oj.uz

Submission #43787

# Submission time Handle Problem Language Result Execution time Memory
43787 2018-03-23T18:46:37 Z evpipis Watching (JOI13_watching) C++11
0 / 100
 316 ms 28652 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 < p)
        ans = max(ans, solve(nex[0][pos], use1+1));
    if (use2 < q)
        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;
    }

    if (q < p)
        for (int i = 1; i <= n; i++){
            swap(nex[0][i], nex[1][i]);
            swap(pre[0][i], pre[1][i]);
        }
    /*if (w == 14){
    for (int i = 1; i <= n; i++)
        printf("i = %d, nex = (%d, %d), pre = (%d, %d)\n", i, nex[0][i], nex[1][i], pre[0][i], pre[1][i]);
    }*/

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= p; j++)
            dp[i][j] = best[i][j] = -1;

    return solve(1, 0);
}

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

    return ans;
}

int main(){
    scanf("%d %d %d", &n, &p, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &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 main()':
watching.cpp:86:34: 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:88:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^
watching.cpp: In function 'int bs()':
watching.cpp:82:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1144 KB Output is correct
2 Correct 2 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 2 ms 1144 KB Output is correct
7 Correct 2 ms 1412 KB Output is correct
8 Correct 2 ms 1420 KB Output is correct
9 Incorrect 3 ms 1420 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16720 KB Output is correct
2 Correct 1 ms 16720 KB Output is correct
3 Correct 2 ms 16720 KB Output is correct
4 Correct 2 ms 16720 KB Output is correct
5 Correct 2 ms 16720 KB Output is correct
6 Correct 2 ms 16720 KB Output is correct
7 Correct 19 ms 16876 KB Output is correct
8 Correct 120 ms 18668 KB Output is correct
9 Incorrect 316 ms 28652 KB Output isn't correct
10 Halted 0 ms 0 KB -