제출 #533135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533135		couplefire	Sparklers (JOI17_sparklers)	C++17	100 / 100	28 ms	2504 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