Submission #970864

#	Time	Username	Problem	Language	Result	Execution time	Memory
970864		vladilius	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	1 ms	348 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define f first
#define s second

pii min(pii x, pii y){
    if (x.f == y.f){
        return {x.f, min(x.s, y.s)};
    }
    if (x.f > y.f) return y;
    return x;
}

signed 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++){
        priority_queue<int, vector<int>, greater<int>> pq;
        int tt = 0, cnt = 0;
        for (int j = i; j <= n; j++){
            pq.push(a[j] - tt);
            int m = pq.top() + tt;
            cnt += (m <= t);
            h[i][j] = cnt;
            tt++;
        }
    }

    auto solve = [&](int m){
        vector<ll> dp(n + 1), cnt(n + 1), l(n + 1);
        dp[1] = h[1][1]; cnt[1] = 0; l[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + (h[l[i - 1]][i] - h[l[i - 1]][i - 1]);
            l[i] = l[i - 1]; cnt[i] = cnt[i - 1];
            
            for (int j = 1; j < i; j++){
                ll nw = dp[j] + h[j + 1][i] + m;
                if (nw < dp[i]){
                    dp[i] = nw;
                    l[i] = j + 1;
                    cnt[i] = cnt[j] + 1;
                }
            }
        }
        pll ret = {dp[n], cnt[n]};
        return ret;
    };
    
    
    int l = 0, r = inf;
    while (l < r){
        int m = (l + r + 1) / 2;
        auto [v, k] = solve(m);
        if (k >= d){
            l = m;
        }
        else {
            r = m - 1;
        }
    }
    
    auto [v, k] = solve(l);
    cout<<v - k * l<<"\n";
}

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