제출 #385682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385682		pit4h	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	364 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve(int n, int k, ll t, vector<int> 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])/2 - 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])/2 - t);
	}
	if(k < n-1 && dp[k+1] + (x[k+1] - x[k]) / 2 > t) {
		return false;
	}
	if(k == 0) return true;
	ll T = (n - 1 - 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) / 2 <= t;
}
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 *= 2;
	vector<int> x(n);
	for(int i=0; i<n; ++i) {
		cin>>x[i];
		x[i] *= 2;
	}
	auto xr = x;
	reverse(xr.begin(), xr.end());
	for(auto& i: xr) {
		i = x[n-1] - i;
	}

	int lo = 0, hi = 1e9 / t + 1;
	while(lo<=hi) {
		int 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