oj.uz

Submission #21039

# Submission time Handle Problem Language Result Execution time Memory
21039 2017-03-31T09:22:26 Z comicalromance Sparklers (JOI17_sparklers) C++11
0 / 100
 0 ms 3580 KB 
#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;
}

Compilation message

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3580 KB Output is correct
2 Correct 0 ms 3580 KB Output is correct
3 Correct 0 ms 3580 KB Output is correct
4 Correct 0 ms 3580 KB Output is correct
5 Correct 0 ms 3580 KB Output is correct
6 Correct 0 ms 3580 KB Output is correct
7 Incorrect 0 ms 3580 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3580 KB Output is correct
2 Correct 0 ms 3580 KB Output is correct
3 Correct 0 ms 3580 KB Output is correct
4 Correct 0 ms 3580 KB Output is correct
5 Correct 0 ms 3580 KB Output is correct
6 Correct 0 ms 3580 KB Output is correct
7 Incorrect 0 ms 3580 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3580 KB Output is correct
2 Correct 0 ms 3580 KB Output is correct
3 Correct 0 ms 3580 KB Output is correct
4 Correct 0 ms 3580 KB Output is correct
5 Correct 0 ms 3580 KB Output is correct
6 Correct 0 ms 3580 KB Output is correct
7 Incorrect 0 ms 3580 KB Output isn't correct
8 Halted 0 ms 0 KB -