oj.uz

Submission #128586

# Submission time Handle Problem Language Result Execution time Memory
128586 2019-07-11T07:12:33 Z jangwonyoung Sparklers (JOI17_sparklers) C++14
0 / 100
 2 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll t;
ll x[100001];
stack<ll>sl,sr;
bool solve(ll s){
	while(!sl.empty()) sl.pop();
	while(!sr.empty()) sr.pop();
	sl.push(8e18);sr.push(8e18);
	for(int i=1; i<k ;i++) sl.push(x[i+1]-x[i]);
	for(int i=n; i>k ;i--) sr.push(x[i]-x[i-1]);
	ll cnt=0;
	for(int i=1; i<n ;i++){
		ll cur=s;
		while(cur>0){
			if(sl.top()<sr.top()){
				if(sl.top()<=cur){
					cur-=sl.top();
					cnt++;
					sl.pop();
				}
				else{
					sl.top()-=cur;cur=0;
				}
			}
			else{
				if(sr.top()<=cur){
					cur-=sr.top();
					cnt++;
					sr.pop();
				}
				else{
					sr.top()-=cur;cur=0;
				}
			}
		}
		if(cnt==0) return false;
		cnt--;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> t;
	for(int i=1; i<=n ;i++){
		cin >> x[i];
	}
	ll l=0,r=1e9;
	while(l!=r){
		ll mid=(l+r)/2;
		if(solve(mid*t*2)) r=mid;
		else l=mid+1;
	}
	cout << l << endl;
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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