oj.uz

Submission #147028

# Submission time Handle Problem Language Result Execution time Memory
147028 2019-08-27T07:43:01 Z ijk1111 Watching (JOI13_watching) C++14
50 / 100
 178 ms 3748 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 2001
int n, p, q, a[N], dp[N][N];

int binsearch(int l, int r, int x) {
        int i = (l+r)/2;

        while (l != i && i != r) {
                if (a[i] <= x)
                        l = i;
                else
                        r = i;

                i = (l+r)/2;
        }

        for (int i = l; i <= r; i++)
                if (a[i] > x)
                        return i;
        return n+1;
}

bool check(int w) {
        for (int i = 0; i <= p; i++)
                for (int j = 0; j <= q; j++)
                        dp[i][j] = 0;

        dp[0][1] = binsearch(1, n, a[1]+2*w-1)-1;
        dp[1][0] = binsearch(1, n, a[1]+w-1)-1;
        for (int i = 1; i <= p; i++)
                for (int j = 1; j <= q; j++) {
                        int tmp1 = binsearch(1, n, a[dp[i-1][j]+1]+w-1) - 1;
                        int tmp2 = binsearch(1, n, a[dp[i][j-1]+1]+2*w-1) - 1;

                        dp[i][j] = max(dp[i-1][j], max(dp[i][j-1], max(tmp1, tmp2)));

                        if (dp[i][j] == n)
                                return true;
                }

        return false;
}

signed main() {
        scanf("%d%d%d", &n, &p, &q);
        for (int i = 1; i <= n; i++)
                scanf("%d", &a[i]);

        if (p+q >= n) {
                printf("%d \n", 1);

                return 0;
        }

        sort(a+1, a+1+n);

        int l = 1, r = 1000000000, ans = 0;

        while (l <= r) {
                int mid = (l+r)/2;

                if (check(mid)) {
                        ans = mid;
                        r = mid-1;
                }
                else l = mid+1;
        }

        printf("%d \n", ans);

        return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:47:14: 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:49:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &a[i]);
                 ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 5 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 428 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 152 ms 1272 KB Output is correct
9 Incorrect 178 ms 3748 KB Output isn't correct
10 Halted 0 ms 0 KB -