oj.uz

Submission #492462

# Submission time Handle Problem Language Result Execution time Memory
492462 2021-12-07T13:02:44 Z ponytail Watching (JOI13_watching) C++17
0 / 100
 217 ms 12100 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
void solve(int tc) {
    int N, P, Q;
    cin >> N >> P >> Q;
    P = min(P, N);
    Q = min(Q, (N+1) / 2);
    int A[N+1];
    for(int i=1; i<=N; i++) cin >> A[i];
    sort(A+1, A+N+1);
    int lb = 1, rb = 1e9;
    while(lb < rb) {
        int w = (lb+rb) >> 1;
        int dp[P+1][Q+1]; // max index we can reach by P small and Q big
        dp[0][0] = 0;
        int sing[N+1], doub[N+1];
        for(int i=1; i<=N; i++) {
            for(int j=i; j<=N; j++) {
                if(A[j] - A[i] + 1 <= w) sing[i] = j;
                if(A[j] - A[i] + 1 <= 2*w) doub[i] = j;
            }
        }
        int idx = 0;
        for(int i=1; i<=P; i++) {
            dp[i][0] = (idx == N ? N : sing[idx + 1]);
            idx = dp[i][0];
        }
        idx = 0;
        for(int i=1; i<=Q; i++) {
            dp[0][i] = (idx == N ? N : doub[idx + 1]);
            idx = dp[0][i];
        }
        for(int i=1; i<=P; i++) {
            for(int j=1; j<=Q; j++) {
                dp[i][j] = max(
                    (dp[i-1][j] == N ? N : sing[dp[i-1][j] + 1]),
                    (dp[i][j-1] == N ? N : doub[dp[i][j-1] + 1])
                );
            }
        }
        if(dp[P][Q] == N) rb = w;
        else lb = w+1;
    }
    cout << lb << "\n";
}
signed main() {
    int t = 1;
    //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 428 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 217 ms 12100 KB Output is correct
4 Correct 82 ms 1484 KB Output is correct
5 Incorrect 73 ms 960 KB Output isn't correct
6 Halted 0 ms 0 KB -