oj.uz

Submission #970865

# Submission time Handle Problem Language Result Execution time Memory
970865 2024-04-27T11:49:50 Z vladilius The short shank; Redemption (BOI21_prison) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -