Submission #57740

#	Time	Username	Problem	Language	Result	Execution time	Memory
57740		spencercompton	Sparklers (JOI17_sparklers)	C++17	50 / 100	79 ms	3944 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll t;
bool v[1001][1001];
ll pos[1001];
// ll dp[2][1000][1000];
// ll pos[1000];
bool go(int l, int r){
	if((pos[r]-pos[l]>2LL*t*(ll)(r-l))){
		return false;
	}
	if(v[l][r]){
		return false;
	}
	if(l==0 && r==n-1){
		return true;
	}
	v[l][r] = true;
	if(l>0 && go(l-1,r)){
		return true;
	}
	if(r<n-1 && go(l,r+1)){
		return true;
	}
	return false;

}
int main(){
	ll tt;
	cin >> n >> k >> tt;
	for(int i = 0; i<n; i++){
		cin >> pos[i];
	}
	k--;
	ll low = 0LL;
	ll high = 1000000000LL;
	while(low<high){
		ll mid = (low+high)/2LL;
		t = mid*tt;
		for(int a = 0; a<1; a++){
			for(int b = 0; b<n; b++){
				for(int c = 0; c<n; c++){
					v[b][c] = false;
				}
			}
		}
		// cout << "! " << low << " " << high << " " << t << " " << endl;
		if(go(k,k)){
			// cout << "A " << endl;
			high = mid;
		}
		else{
			// cout << "B " << endl;
			low = mid+1;
		}
	}
	cout << low << endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50