Submission #1086890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086890	2024-09-11T16:37:21 Z	pokmui9909	Sparklers (JOI17_sparklers)	C++17	0 / 100	14 ms	16516 KB

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];
    }
    ll L = 0, 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

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8284 KB	Output is correct
2	Correct	8 ms	8284 KB	Output is correct
3	Correct	8 ms	8284 KB	Output is correct
4	Correct	8 ms	8284 KB	Output is correct
5	Correct	8 ms	8284 KB	Output is correct
6	Correct	8 ms	8232 KB	Output is correct
7	Correct	8 ms	8284 KB	Output is correct
8	Correct	9 ms	8284 KB	Output is correct
9	Correct	9 ms	8284 KB	Output is correct
10	Correct	8 ms	8240 KB	Output is correct
11	Correct	8 ms	8284 KB	Output is correct
12	Correct	8 ms	8284 KB	Output is correct
13	Correct	8 ms	8284 KB	Output is correct
14	Correct	9 ms	8284 KB	Output is correct
15	Correct	8 ms	8284 KB	Output is correct
16	Correct	8 ms	8284 KB	Output is correct
17	Correct	8 ms	8284 KB	Output is correct
18	Correct	8 ms	8372 KB	Output is correct
19	Runtime error	14 ms	16516 KB	Execution killed with signal 8
20	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8284 KB	Output is correct
2	Correct	8 ms	8284 KB	Output is correct
3	Correct	8 ms	8284 KB	Output is correct
4	Correct	8 ms	8284 KB	Output is correct
5	Correct	8 ms	8284 KB	Output is correct
6	Correct	8 ms	8232 KB	Output is correct
7	Correct	8 ms	8284 KB	Output is correct
8	Correct	9 ms	8284 KB	Output is correct
9	Correct	9 ms	8284 KB	Output is correct
10	Correct	8 ms	8240 KB	Output is correct
11	Correct	8 ms	8284 KB	Output is correct
12	Correct	8 ms	8284 KB	Output is correct
13	Correct	8 ms	8284 KB	Output is correct
14	Correct	9 ms	8284 KB	Output is correct
15	Correct	8 ms	8284 KB	Output is correct
16	Correct	8 ms	8284 KB	Output is correct
17	Correct	8 ms	8284 KB	Output is correct
18	Correct	8 ms	8372 KB	Output is correct
19	Runtime error	14 ms	16516 KB	Execution killed with signal 8
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8284 KB	Output is correct
2	Correct	8 ms	8284 KB	Output is correct
3	Correct	8 ms	8284 KB	Output is correct
4	Correct	8 ms	8284 KB	Output is correct
5	Correct	8 ms	8284 KB	Output is correct
6	Correct	8 ms	8232 KB	Output is correct
7	Correct	8 ms	8284 KB	Output is correct
8	Correct	9 ms	8284 KB	Output is correct
9	Correct	9 ms	8284 KB	Output is correct
10	Correct	8 ms	8240 KB	Output is correct
11	Correct	8 ms	8284 KB	Output is correct
12	Correct	8 ms	8284 KB	Output is correct
13	Correct	8 ms	8284 KB	Output is correct
14	Correct	9 ms	8284 KB	Output is correct
15	Correct	8 ms	8284 KB	Output is correct
16	Correct	8 ms	8284 KB	Output is correct
17	Correct	8 ms	8284 KB	Output is correct
18	Correct	8 ms	8372 KB	Output is correct
19	Runtime error	14 ms	16516 KB	Execution killed with signal 8
20	Halted	0 ms	0 KB	-