Submission #1294874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294874		kian2009	Sparklers (JOI17_sparklers)	C++20	50 / 100	17 ms	1344 KiB

sparklers

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

typedef long long ll;

const int MAXN = 1e3 + 10;

ll n, k, t, x[MAXN];
bool dp[MAXN][MAXN];
vector<ll> h1, h2, h;

void input() {
	cin >> n >> k >> t;
	--k;
	for (int i = 0; i < n; i++)
		cin >> x[i];
}

bool check(ll s) {
	for (int i = 0; i <= k; i++)
		for (int j = k; j < n; j++)
			dp[i][j] = false;
	dp[k][k] = true;
	for (int i = k; i >= 0; i--)
		for (int j = k; j < n; j++) {
			ll r = (j - i + 1) * s - (x[j] - x[i]);
			if (i && r >= x[i] - x[i - 1])
				dp[i - 1][j] |= dp[i][j];
			if (j < (n - 1) && r >= x[j + 1] - x[j])
				dp[i][j + 1] |= dp[i][j];
		}
	return dp[0][n - 1];
}

ll findAns() {
	ll l = -1, r = x[n - 1];
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (check(2 * mid * t))
			r = mid;
		else
			l = mid;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	if (n == 1)
		cout << 0 << endl;
	else
		cout << findAns() << endl;
	return 0;
}

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