oj.uz

Submission #970919

# Submission time Handle Problem Language Result Execution time Memory
970919 2024-04-27T14:12:58 Z vladilius The short shank; Redemption (BOI21_prison) C++17
0 / 100
 231 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll infll = 1e18;
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;
}

ll min(ll x, ll y){
    if (x < y) return x;
    return y;
}

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++){
        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 = [&](ld m){
        vector<vector<ld>> dp(n + 1, vector<ld>(2));
        vector<vector<int>> l(n + 1, vector<int>(2)), cnt(n + 1, vector<int>(2));
        // dp[i][0] - продовжувати попередній
        // dp[i][1] - створити новий
        
        dp[1][0] = infll;
        dp[1][1] = h[1][1];
        cnt[1][1] = 0;
        l[1][1] = 1;
        
        for (int i = 2; i <= n; i++){
            ld v1 = infll, v2 = infll;
            if (l[i - 1][0]) v1 = dp[l[i - 1][0]][1] + h[l[i - 1][0]][i] - h[l[i - 1][0]][l[i - 1][0]];
            if (l[i - 1][1]) v2 = dp[l[i - 1][1]][1] + h[l[i - 1][1]][i] - h[l[i - 1][1]][l[i - 1][1]];
            if (v1 < v2){
                dp[i][0] = v1;
                l[i][0] = l[i - 1][0];
                cnt[i][0] = cnt[i - 1][0];
            }
            else {
                dp[i][0] = v2;
                l[i][0] = l[i - 1][1];
                cnt[i][0] = cnt[i - 1][1];
            }
            
            v1 = dp[i - 1][0] + h[i][i] + m;
            v2 = dp[i - 1][1] + h[i][i] + m;
            if (v1 < v2){
                dp[i][1] = v1;
                l[i][1] = i;
                cnt[i][1] = cnt[i - 1][0] + 1;
            }
            else {
                dp[i][1] = v2;
                l[i][1] = i;
                cnt[i][1] = cnt[i - 1][1] + 1;
            }
        }
        
        /*
        for (int i = 1; i <= n; i++){
            cout<<dp[i][0]<<" "<<cnt[i][0]<<"\n";
        }
        cout<<"\n";
        for (int i = 1; i <= n; i++){
            cout<<dp[i][1]<<" "<<cnt[i][1]<<"\n";
        }
         */

        return min({dp[n][0], cnt[n][0]}, {dp[n][1], cnt[n][1]});
    };
    

    ld l = 0, r = n;
    int tt = 100;
    while (tt--){
        ld m = (l + r) / 2;
        auto [v, k] = solve(m);
        if (k > d){
            l = m;
        }
        else {
            r = m;
        }
    }
    
    auto [v1, k1] = solve(l);
    auto [v2, k2] = solve(r);
    // cout<<fixed<<setprecision(20)<<l<<" "<<v1<<" "<<k1<<"\n";
    // cout<<fixed<<setprecision(20)<<r<<" "<<v2<<" "<<k2<<"\n";

    ld out = n + 1;
    if (k1 <= d) out = min(out, v1 - k1 * l);
    if (k2 <= d) out = min(out, v2 - k2 * r);
    cout<<out<<"\n";
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 231 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 192 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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

Subtask #6
0 / 20.0

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