Submission #1233166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233166		PenguinsAreCute	Sparklers (JOI17_sparklers)	C++17	50 / 100	167 ms	327680 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k, t;
	cin >> n >> k >> t;
	k--;
	int x[n];
	for(int i=0;i<n;i++)
		cin >> x[i];
	int l = -1, h = (1e9 / t) + 1;
	while(h - l > 1) {
		int s = (l + h) / 2;
		int d = s * t;
		bool reach[n][n];
		memset(reach,0,sizeof(reach));
		reach[k][k] = 1;
		for(int l=k;~l;l--)
			for(int r=k;r<n;r++)
				if(reach[l][r]) {
					if(r+1<n && x[r+1] - x[l] <= 2LL * (r - l + 1) * d)
						reach[l][r+1] = 1;
					if(l && x[r] - x[l-1] <= 2LL * (r - l + 1) * d)
						reach[l-1][r] = 1;
				}
		if(reach[0][n-1])
			h = s;
		else
			l = s;
	}
	cout << h;
}

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