Submission #1086894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086894		pokmui9909	Sparklers (JOI17_sparklers)	C++17	50 / 100	21 ms	18268 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, K, T, A[100005];
ll D[1005][1005];

void f(ll s, ll e, ll v){
    if(s >= 2 && D[s - 1][e] == -1){
        if((A[e] - A[s - 1] + 2 * v - 1) / 2 / v <= (e - s + 1) * T){
            D[s - 1][e] = 1;
            f(s - 1, e, v);
        } else {
            D[s - 1][e] = 0;
        }
    }
    if(e < N && D[s][e + 1] == -1){
        if((A[e + 1] - A[s] + 2 * v - 1) / 2 / v <= (e - s + 1) * T){
            D[s][e + 1] = 1;
            f(s, e + 1, v);
        } else {
            D[s][e + 1] = 0;
        }
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N >> K >> T;
    for(ll i = 1; i <= N; i++){
        cin >> A[i];
    }
    if(A[N] == 0){
        cout << 0; return 0;
    }
    ll L = 1, R = 1e9;
    while(L <= R){
        ll m = (L + R) / 2;
        fill(D[0], D[1004] + 1005, -1LL);
        D[K][K] = 1;
        f(K, K, m);
        if(D[1][N] == 1) R = m - 1;
        else L = m + 1;
    }
    cout << L;
}

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