Submission #168997

#	Time	Username	Problem	Language	Result	Execution time	Memory
168997		combi1k1	Sparklers (JOI17_sparklers)	C++14	100 / 100	29 ms	2564 KiB

sparklers

#include<bits/stdc++.h>

using namespace std;

#define ll  long long

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;
    int T;  cin >> T;   k--;

    vector<int> v(n);
    vector<ll>  d(n);

    auto check = [&](int m) {
        for(int i = 0 ; i < n ; ++i)
            d[i] = 2ll * T * i * m - v[i];

        int pl = k, nl = k - 1;
        int pr = k, nr = k + 1;

        while (1)   {
            while (d[nl] > d[pl] && d[nl] <= d[pr] && nl > 0)       nl--;
            while (d[nr] < d[pr] && d[nr] >= d[pl] && nr < n - 1)   nr++;

            bool ok = 0;

            if (nl >= 0 && d[nl] <= d[pl])  pl = nl--, ok = 1;
            if (nr <  n && d[nr] >= d[pr])  pr = nr++, ok = 1;

            if(!ok) break;
        }
        if (nr <  n && d[pl] > d[nr])   return  false;
        if (nl >= 0 && d[pr] < d[nl])   return  false;

        int l = 0;      nl = 1;
        int r = n - 1;  nr = n - 2;

        while (1)   {
            while (d[nl] > d[l] && d[nl] <= d[r] && nl < k) nl++;
            while (d[nr] < d[r] && d[nr] >= d[l] && nr > k) nr--;

            bool ok = 0;

            if (nl <= k && d[nl] <= d[l])   l = nl++, ok = 1;
            if (nr >= k && d[nr] >= d[r])   r = nr--, ok = 1;

            if(!ok) break;
        }

        return  pl <= l && r <= pr;
    };

    for(int&x : v)
        cin >> x;

    int l = 0;
    int r = 1e9;

    for(; l < r ;)  {
        int m = (l + r) / 2;

        if (check(m))
            r = m;
        else
            l = m + 1;
    }

    cout << l << endl;
}

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