Submission #1197890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197890		og_matveychick1	Sparklers (JOI17_sparklers)	C++20	0 / 100	1 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;
    while (l != 0 || r != n - 1) {
        if (l > 0 && b[l - 1] >= b[r]) l--;
        else if (r < n - 1 && b[r + 1] <= b[l]) 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(3);
    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