제출 #1214903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214903		JooDdae	Sparklers (JOI17_sparklers)	C++20	0 / 100	6 ms	4424 KiB

sparklers

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

int n, k, t, a[100100], dp[1010][1010];

bool solve(int mid) {
	memset(dp, 0, sizeof dp);
	dp[k][k] = 1;
	for(int l=2;l<=n;l++) {
		for(int i=1;i<=n-l+1;i++) {
			int j = i+l-1;
			
			if(a[j]-a[i] <= 1ll*(j-i)*t * 2*mid) {
				dp[i][j] = dp[i+1][j] | dp[i][j-1];
			}
		}
	}
	return dp[1][n];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k >> t;
	for(int i=1;i<=n;i++) cin >> a[i];

	int l = 1, r = 1e9;
	while(l <= r) {
		int mid = (l+r)/2;
		if(solve(mid)) r = mid-1;
		else l = mid+1;
	}
	cout << l;
}

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