oj.uz

Submission #385742

# Submission time Handle Problem Language Result Execution time Memory
385742 2021-04-04T20:45:23 Z pit4h Sparklers (JOI17_sparklers) C++14
0 / 100
 1 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve(int n, int k, ll t, vector<ll> x) {
	if(k<0 || k>=n) return false;	
	vector<ll> dp(n);
	dp[0] = 0;
	for(int i=1; i<k; ++i) {
		dp[i] = max((ll)0, dp[i-1] + (x[i] - x[i-1])/2LL - t);	
	}
	dp[n-1] = 0;
	for(int i=n-2; i>k; --i) {
		dp[i] = max((ll)0, dp[i+1] + (x[i+1] - x[i])/2LL - t);
	}
	if(k < n-1 && dp[k+1] + (x[k+1] - x[k]) / 2LL > t) {
		return false;
	}
	if(k == 0) return true;
	ll T = (ll)(n - k) * t;
	ll p1 = x[n-1] - T;	
	ll p2 = x[k-1] - min(dp[k-1], T) + max(0LL, T - dp[k-1]);
	return p1 <= p2;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k;
	ll t;
	cin>>n>>k>>t;
	k--;
	t *= 4LL;
	vector<ll> x(n);
	for(int i=0; i<n; ++i) {
		cin>>x[i];
		x[i] *= 4LL;
	}
	auto xr = x;
	reverse(xr.begin(), xr.end());
	for(auto& i: xr) {
		i = x[n-1] - i;
	}

	ll lo = 0, hi = 1e12 / t + 1;
	while(lo<=hi) {
		ll mid = (lo+hi)/2LL;
		//if(solve(n, k, t*mid, x) || solve(n, n-k-1, t*mid, xr) || solve(n, k-1, t*mid, x) || solve(n, n-(k+1)-1, t*mid, xr)) {
		if(solve(n, k, t*mid, x) || solve(n, n-k-1, t*mid, xr)) {
			hi = mid-1;
		}
		else {
			lo = mid+1;
		}
	}
	cout<<hi+1<<'\n';
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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