Submission #21039

#	Time	Username	Problem	Language	Result	Execution time	Memory
21039		comicalromance	Sparklers (JOI17_sparklers)	C++11	0 / 100	0 ms	3580 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
long long a[100005], s[100005],n,k, t;
bool check(int v) {
    //cout<<"CHECKING "<<v<<endl;
    long long l=k-1,r=k, tl=1,dist=0;
    while(l!=0 || r!=n) {
        //cout<<s[l]<<" "<<s[r]<<endl;
        if(s[l] > s[r]) {
            if(2*v*t*tl < s[r]+dist) return false;
            tl++;
            dist+=s[r];
            r++;
        }
        else {
            if(2*v*t*tl < s[l]+dist) return false;
            tl++;
            dist+=s[l];
            l--;
        }
    }
    return true;
}
int main() {
    long long i;
    //ifstream cin("03-27.txt", ifstream::in);
    //ofstream cout("ans.txt", ofstream::out);
    cin>>n>>k>>t;
    for(i=1;i<=n;i++) {
        cin>>a[i];
        s[i-1] = a[i] - a[i-1];
    }
    s[0] = s[n] = 1e9;
    long long h=a[n],l=0,m=(h+l)/2;
    while(h-l>1) {
        if(check(m)) h=m;
        else l=m;
        m = (h+l)/2;
    }
    cout<<h;
}

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