Submission #1294923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294923		Hamed_Ghaffari	Sparklers (JOI17_sparklers)	C++20	50 / 100	21 ms	1344 KiB

sparklers

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

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 1e3+5;

int n, k;
ll t, x[MXN];
bool dp[MXN][MXN];

bool check(ll s) {
    dp[k][k] = 1;
    for(int ln=2; ln<=n; ln++)
        for(int l=max(1, k-ln+1), r=l+ln-1; r<=n && r<=k+ln-1; l++, r++) {
            dp[l][r] = 0;
            if(__lg(r-l) + __lg(t*s*2) < 40 && (x[r]-x[l]) > (r-l)*t*s*2) continue;
            dp[l][r] = dp[l+1][r] | dp[l][r-1];
        }
    return dp[1][n];
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k >> t;
    for(int i=1; i<=n; i++) cin >> x[i];
    int l=0, r=x[n];
    while(r-l>1)
        (check(mid) ? r : l) = mid;
    cout << r << '\n';
    return 0;
}

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