제출 #1130274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130274		juliany2	Sparklers (JOI17_sparklers)	C++20	50 / 100	16 ms	8384 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 1e3 + 7;
int n, k;
ll t, a[N];
ll dp[N][N];

ll cdiv(ll x, ll y) {
    if (y == 0) return 0;
    return (x + y - 1) / y;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> k >> t;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    memset(dp, 0x3f, sizeof(dp));
    dp[0][n] = 0;

    for (int l = 1; l <= n; l++) {
        for (int r = n; r >= 1; r--) {
            dp[l][r] = max(cdiv(a[r] - a[l], 2 * t * (r - l)), min(dp[l - 1][r], dp[l][r + 1]));
        }
    }

    cout << dp[k][k] << '\n';

    return 0;
}

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