Submission #1197892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197892		og_matveychick1	Sparklers (JOI17_sparklers)	C++20	0 / 100	0 ms	328 KiB

sparklers

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll N = 1e5 + 5;

ll n, k, t, a[N], b[N];

bool check(ll s) {
    if (s * t > 1e9) return 1;
    for (ll i = 0; i < n; i++) b[i] = a[i] - 2 * s * t * i;
    ll l = k, r = k, L = b[k], R = b[k];
    while (l != 0 || r != n - 1) {
        if (l > 0 && b[l - 1] >= R) l--, L = max(L, b[l]);
        else if (r < n - 1 && b[r + 1] <= L) r++, R = min(R, b[r]);
        else return 0;
    }
    return 1;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k >> t, k--;
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll l = -1, r = 1e9 / t + 5;
    check(2);
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        (check(m) ? r : l) = m;
    }
    cout << r;
}

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