Submission #986929

#	Time	Username	Problem	Language	Result	Execution time	Memory
986929		alextodoran	Sparklers (JOI17_sparklers)	C++17	50 / 100	21 ms	1372 KiB

sparklers

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N_MAX = 1000;

int N, K, T;
int X[N_MAX + 2];

bool dp[N_MAX + 2][N_MAX + 2];

bool check (int speed) {
    dp[1][N] = true;
    for (int l = 1; l <= K; l++) {
        for (int r = N - (l == 1); r >= K; r--) {
            dp[l][r] = false;
            if (l > 1 && X[r] - X[l - 1] <= (ll) speed * (r - l + 1) * 2 * T) {
                dp[l][r] |= dp[l - 1][r];
            }
            if (r < N && X[r + 1] - X[l] <= (ll) speed * (r - l + 1) * 2 * T) {
                dp[l][r] |= dp[l][r + 1];
            }
        }
    }
    return dp[K][K];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K >> T;
    for (int i = 1; i <= N; i++) {
        cin >> X[i];
    }
    int l = 0, r = (int) 1e9 / T + 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid) == true) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << "\n";

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50