Submission #972380

#	Time	Username	Problem	Language	Result	Execution time	Memory
972380		idas	The short shank; Redemption (BOI21_prison)	C++11	35 / 100	1139 ms	176548 KiB

prison

#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF=1e9;

const int N=4010, D=4010;
int n, d, T, r[N], mx[N], dp[N][D], t[4*N][D], lazy[4*N][D];

void push(int id, int in)
{
    t[id][in]+=lazy[id][in];
    if(id*2+1<4*N){
        lazy[id*2][in]+=lazy[id][in];
        lazy[id*2+1][in]+=lazy[id][in];
    }
//    else if(id*2<4*N){
//        lazy[id*2][in]+=lazy[id][in];
//    }
    lazy[id][in]=0;
}

void add(int x, int y, int in, int val, int l=0, int r=n, int id=1)
{
    push(id, in);
    if(r<x||l>y) return;
    if(x<=l&&r<=y){
        lazy[id][in]+=val;
        push(id, in);
        return;
    }
    int m=(l+r)/2;
    add(x, y, in, val, l, m, id*2);
    add(x, y, in, val, m+1, r, id*2+1);
    t[id][in]=min(t[id*2][in], t[id*2+1][in]);
}

int get(int x, int y, int in, int l=0, int r=n, int id=1)
{
    push(id, in);
    if(r<x||l>y) return INF;
    if(x<=l&&r<=y) return t[id][in];
    int m=(l+r)/2;
    int k=min(get(x, y, in, l, m, id*2), get(x, y, in, m+1, r, id*2+1));
    t[id][in]=min(t[id*2][in], t[id*2+1][in]);
    return k;
}

vector<pii> inf;
void build()
{
    FOR(i, 1, n+1) mx[i]=-1;

    sort(inf.begin(), inf.end());

    set<int, greater<int>> st;
    for(int i=n; i>=1; i--){
        while(!inf.empty() && (inf.back()).f==i){
            pii u=inf.back(); inf.pop_back();
            st.insert(u.s);
        }

        if(!st.empty()){
            mx[i]=*st.begin();
        }

        st.erase(i);
    }
}

int main()
{
    FAST_IO;
    cin >> n >> d >> T;

    FOR(i, 1, n+1)
    {
        int t; cin >> t;
        if(t>T) r[i]=-1;
        else r[i]=min(n, i+T-t);
        inf.pb({r[i],i});
    }
    build();

    FOR(i, 0, n+1) FOR(j, 0, d+2) dp[i][j]=INF;
//    FOR(i, 0, 4*N) FOR(j, 0, D) t[i][j]=INF;
    dp[0][0]=0;

//    FOR(i, 1, n+1)
//    {
//        cout << mx[i] << " ";
//    }
//    cout << '\n';

    FOR(i, 1, n+1)
    {
        if(mx[i]!=-1) add(0, 0, 0, 1);
        dp[i][1]=min(dp[i][1], get(0, 0, 0));
        add(i, i, 1, dp[i][1]);

//        cout << i << " " << dp[i][1] << '\n';

        FOR(j, 2, d+2)
        {
            if(mx[i]!=-1) add(0, mx[i]-1, j-1, 1);
            dp[i][j]=min(dp[i][j], get(0, i-1, j-1));
            dp[i][j]=min(dp[i][j], dp[i][j-1]);
            add(i, i, j, dp[i][j]);
        }
    }

//    assert(dp[n][d+1]!=INF);
//
    cout << dp[n][d+1];
}

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