oj.uz

Submission #1086887

# Submission time Handle Problem Language Result Execution time Memory
1086887 2024-09-11T16:33:54 Z pokmui9909 Sparklers (JOI17_sparklers) C++17
0 / 100
 13 ms 8372 KB 
#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 = 1, R = 1e15;
    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 12 ms 8284 KB Output is correct
2 Correct 13 ms 8368 KB Output is correct
3 Correct 13 ms 8284 KB Output is correct
4 Correct 12 ms 8284 KB Output is correct
5 Correct 12 ms 8372 KB Output is correct
6 Correct 11 ms 8284 KB Output is correct
7 Correct 13 ms 8284 KB Output is correct
8 Correct 13 ms 8284 KB Output is correct
9 Correct 12 ms 8368 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 13 ms 8372 KB Output is correct
12 Correct 11 ms 8280 KB Output is correct
13 Correct 12 ms 8280 KB Output is correct
14 Correct 13 ms 8284 KB Output is correct
15 Correct 12 ms 8284 KB Output is correct
16 Correct 12 ms 8372 KB Output is correct
17 Correct 12 ms 8284 KB Output is correct
18 Correct 11 ms 8284 KB Output is correct
19 Incorrect 11 ms 8284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8284 KB Output is correct
2 Correct 13 ms 8368 KB Output is correct
3 Correct 13 ms 8284 KB Output is correct
4 Correct 12 ms 8284 KB Output is correct
5 Correct 12 ms 8372 KB Output is correct
6 Correct 11 ms 8284 KB Output is correct
7 Correct 13 ms 8284 KB Output is correct
8 Correct 13 ms 8284 KB Output is correct
9 Correct 12 ms 8368 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 13 ms 8372 KB Output is correct
12 Correct 11 ms 8280 KB Output is correct
13 Correct 12 ms 8280 KB Output is correct
14 Correct 13 ms 8284 KB Output is correct
15 Correct 12 ms 8284 KB Output is correct
16 Correct 12 ms 8372 KB Output is correct
17 Correct 12 ms 8284 KB Output is correct
18 Correct 11 ms 8284 KB Output is correct
19 Incorrect 11 ms 8284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8284 KB Output is correct
2 Correct 13 ms 8368 KB Output is correct
3 Correct 13 ms 8284 KB Output is correct
4 Correct 12 ms 8284 KB Output is correct
5 Correct 12 ms 8372 KB Output is correct
6 Correct 11 ms 8284 KB Output is correct
7 Correct 13 ms 8284 KB Output is correct
8 Correct 13 ms 8284 KB Output is correct
9 Correct 12 ms 8368 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 13 ms 8372 KB Output is correct
12 Correct 11 ms 8280 KB Output is correct
13 Correct 12 ms 8280 KB Output is correct
14 Correct 13 ms 8284 KB Output is correct
15 Correct 12 ms 8284 KB Output is correct
16 Correct 12 ms 8372 KB Output is correct
17 Correct 12 ms 8284 KB Output is correct
18 Correct 11 ms 8284 KB Output is correct
19 Incorrect 11 ms 8284 KB Output isn't correct
20 Halted 0 ms 0 KB -