oj.uz

Submission #51414

# Submission time Handle Problem Language Result Execution time Memory
51414 2018-06-18T01:20:34 Z FutymyClone Watching (JOI13_watching) C++14
0 / 100
 91 ms 16364 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
int dp[N][N], a[N], n, p, q;

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

    if (p >= n) printf("%d", 1);
    else {

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

        int l = 1;
        int r = 1000000000;

        while (l <= r) {
            int mid = (l + r)/2;
            memset(dp, 0x3f, sizeof(dp));
            dp[0][0] = 0;
            dp[1][0] = 1;
            dp[1][1] = 0;
            int pt = 1;
            int pt2 = 1;

            for (int i = 2; i <= n; i++) {
                for (int j = 0; j <= p; j++) {
                    if (j) {
                        while (a[pt] + mid <= a[i]) pt++;
                        pt--;
                        pt = max(pt, 1);

                        dp[i][j] = min(dp[i][j], dp[pt][j - 1]);
                    }

                    while (a[pt2] + 2 * mid <= a[i]) pt2++;
                    pt2--;
                    pt2 = max(pt2, 1);

                    dp[i][j] = min(dp[i][j], dp[pt2][j] + 1);
                }
            }

            int mn = 0x3f3f3f3f;
            for (int i = 0; i <= p; i++) mn = min(mn, dp[n][q]);

            if (mn <= q) r = mid - 1;
            else l = mid + 1;
        }

        #ifdef Futymy
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= p; j++) {
                cout << dp[i][j] << " ";
            }
            cout << "\n";
        }
        #endif // Futymy

        printf("%d", l);
    }
    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:9:10: 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:10:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 16364 KB Output isn't correct
2 Halted 0 ms 0 KB -