Submission #478626

#	Time	Username	Problem	Language	Result	Execution time	Memory
478626		Haruto810198	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	2077 ms	11952 KiB

prison

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 2000010;

int n, d, T;

int segs;
vector<pii> seg; // id. of seg : 0-indexed
vi dis_prev;
vi pref;

vector<vi> dp;

int query(int ql, int qr){
    if(ql > qr) return 0;
    if(ql == 0) return pref[qr];
    return pref[qr] - pref[ql - 1];
}

void solve(int u, int sl, int sr, int optl, int optr){
    int mid = (sl + sr) / 2;
    int optmid, Max = -INF;
    FOR(i, optl, optr, 1){
        int val = dp[u - 1][i] + query(i + 2, mid) + max((int)0, seg[i+1].F - seg[i].F - 1);
        if(val > Max){
            Max = val;
            optmid = i;
        }
    }
    dp[u][mid] = Max;
    //cerr<<"dp["<<u<<"]["<<mid<<"] = "<<dp[u][mid]<<", opt = dp["<<u-1<<"]["<<optmid<<"] "<<endl;
    if(sl <= mid-1) solve(u, sl, mid-1, optl, optr); //solve(u, sl, mid-1, optl, optmid);
    if(mid+1 <= sr) solve(u, mid+1, sr, optl, optr); //solve(u, mid+1, sr, optmid, optr);
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>d>>T;
    FOR(i, 1, n, 1){
        int ti;
        cin>>ti;
        if(ti <= T){
            int len = T - ti;
            seg.eb(i, min(i + len, n));
        }
    }

    segs = szof(seg);
    dis_prev.resize(segs);

    if(segs == 0){
        cout<<0<<'\n';
        return 0;
    }

    //
    seg.eb(n+1, n+1);
    //

    dis_prev[0] = 0;
    FOR(i, 1, segs - 1, 1){
        dis_prev[i] = max((int)0, seg[i].F - seg[i-1].S - 1);
    }

    pref.resize(segs);
    pref[0] = dis_prev[0];
    FOR(i, 1, segs - 1, 1){
        pref[i] = pref[i-1] + dis_prev[i];
    }

    dp.resize(d + 1);
    for(vi& i : dp){
        i.resize(segs);
    }

    FOR(i, 0, segs - 1, 1){
        dp[1][i] = query(1, i);
    }

    FOR(i, 0, segs - 1, 1){
        //cerr<<"dp[1]["<<i<<"] = "<<dp[1][i]<<endl;
    }

    d = min(d, segs);
    FOR(i, 2, d, 1){
        solve(i, i-1, segs-1, i-2, segs-2);
        FOR(j, 0, segs - 1, 1){
            //cerr<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<" ";
        }
        //cerr<<endl;
    }
    //cerr<<endl;

    int res = -INF;
    FOR(i, d - 1, segs - 1, 1){
        res = max(res, dp[d][i] + query(i + 2, segs - 1) + max((int)0, seg[i+1].F - seg[i].F - 1));
    }

    res = n - res;
    cout<<res<<'\n';

    return 0;

}

Compilation message (stderr)

prison.cpp: In function 'void solve(long long int, long long int, long long int, long long int, long long int)':
prison.cpp:49:9: warning: variable 'optmid' set but not used [-Wunused-but-set-variable]
   49 |     int optmid, Max = -INF;
      |         ^~~~~~

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