Submission #385731

#	Time	Username	Problem	Language	Result	Execution time	Memory
385731		pit4h	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	372 KiB

sparklers

#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;
	}
	vector<ll> tmp;
	for(int i=0; i<n; ++i) {
		if(i==k || x[i] != x[k]) {
			tmp.push_back(x[i]);
		}
		if(i==k) k = tmp.size()-1;
	}
	x = tmp;
	n = x.size();
	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)/2;
		//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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50