제출 #971032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971032		vladilius	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2052 ms	524288 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ld, int>;
#define f first
#define s second

bool operator < (pll x, pll y){
    if (x.f == y.f){
        return x.s < y.s;
    }
    if (x.f > y.f) return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, d, t; cin>>n>>d>>t;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    
    vector<vector<int>> h(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++){
        int mx = 0, cnt = 0;
        for (int j = i; j <= n; j++){
            if (a[j] <= t){
                int m = t - a[j];
                mx = max(mx, j + m);
            }
            cnt += (j <= mx);
            h[i][j] = cnt;
        }
    }

    auto solve = [&](ld m){
        pll dp[n + 1];
        for (int i = 1; i <= n; i++){
            dp[i] = {h[1][i], 0};
            for (int j = 1; j < i; j++){
                // [1, j] | [j + 1, i]
                dp[i] = min(dp[i], {dp[j].f + h[j + 1][i] + m, dp[j].s + 1});
            }
        }

        return dp[n];
    };
    
    ld l = 0, r = n;
    int tt = 30;
    while (tt--){
        ld m = (l + r) / 2;
        auto [v, k] = solve(m);
        if (k > d){
            l = m;
        }
        else {
            r = m;
        }
    }
    
    auto [v, k] = solve(l);
    cout<<round(v - l * d)<<"\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20