oj.uz

Submission #972386

# Submission time Handle Problem Language Result Execution time Memory
972386 2024-04-30T11:36:34 Z idas The short shank; Redemption (BOI21_prison) C++11
10 / 100
 1025 ms 97940 KB 
#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=5e5+10, D=5;
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];
    }
    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;
    dp[0][0]=0;

    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]);

        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
0 / 15.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1025 ms 91432 KB Output is correct
3 Correct 993 ms 97940 KB Output is correct
4 Correct 973 ms 89224 KB Output is correct
5 Correct 900 ms 79900 KB Output is correct
6 Correct 818 ms 81772 KB Output is correct
7 Correct 897 ms 82128 KB Output is correct
8 Correct 859 ms 81772 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 3 ms 8540 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 8540 KB Output is correct
2 Incorrect 873 ms 26496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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

Subtask #6
0 / 20.0

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