Submission #465136

#	Time	Username	Problem	Language	Result	Execution time	Memory
465136		MahdiBahramian	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	749 ms	14020 KiB

prison

#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define mt make_tuple
using namespace std;
const int Max = 2e6 + 10 , INF = 1e9 + 10;
int n , t;
int A[Max];
long double dp[Max]; int last[Max] , cnt[Max];
void CALC(long double tst)
{
    last[0] = INF;
    for(int i = 1 ; i <= n ; i++)
    {
        dp[i] = dp[i - 1] + tst + int(A[i] <= t);
        cnt[i] = cnt[i - 1] + 1;
        last[i] = A[i];

        if(dp[i] > dp[i - 1] + int(min(last[i - 1] + 1 , A[i]) <= t))
        {
            dp[i] = dp[i - 1] + int(min(last[i - 1] + 1 , A[i]) <= t);
            cnt[i] = cnt[i - 1];
            last[i] = min(last[i - 1] + 1 , A[i]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int d; cin >> n >> d >> t;
    for(int i = 1 ; i <= n ; i++) cin >> A[i];

    long double l = 1e9 , r = -1e9;
    for(int lg = 0 ; lg < 100 ; lg++)
    {
        long double md = (l + r) / 2;
        CALC(md);
        if(cnt[n] > d) r = md;
        else l = md;
    }
    CALC(l);
    //assert(cnt[n] == d);
    cout << round(dp[n] - l * cnt[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