Submission #55327

#	Time	Username	Problem	Language	Result	Execution time	Memory
55327		ksun48	Sparklers (JOI17_sparklers)	C++14	50 / 100	37 ms	5512 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	LL n, k, t;
	cin >> n >> k >> t;
	k--;
	vector<LL> x(n);
	for(int i = 0; i < n; i++){
		cin >> x[i];
	}
	sort(x.begin(), x.end());
	LL equal = 1;
	for(int i = 0; i < n; i++){
		if(x[i] != x[i]){
			equal = 0;
		}
	}

	LL s = -1; // cant
	LL e = 1000000000;
	while(s + 1 < e){
		LL m = (s + e) / 2;
		LL cover = m * t * 2;
		LL dp[n][n];
		for(LL i = k; i >= 0; i--){
			for(LL j = k; j < n; j++){
				dp[i][j] = 0;
				if(x[j]-x[i] > (j-i) * cover){
					continue;
				}
				if(i == k && j == k){
					dp[i][j] = 1;
					continue;
				}
				if(i < k && dp[i+1][j]){
					dp[i][j] = 1;
				}
				if(j > k && dp[i][j-1]){
					dp[i][j] = 1;
				}
			}
		}
		if(dp[0][n-1]){
			e = m;
		} else {
			s = m;
		}
	}
	cout << e << '\n';
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:15:5: warning: variable 'equal' set but not used [-Wunused-but-set-variable]
  LL equal = 1;
     ^~~~~

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