oj.uz

Submission #411551

# Submission time Handle Problem Language Result Execution time Memory
411551 2021-05-25T13:46:44 Z 반딧불(#7604) The short shank; Redemption (BOI21_prison) C++17
15 / 100
 349 ms 170032 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick {
    int n;
    int tree[2000002];
    Fenwick(){}

    void init(int _n){
        n = _n;
    }
    void add(int x, int y){
        while(x <= n){
            tree[x] += y;
            x += x&-x;
        }
    }
    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
    int sum(int l, int r){
        return sum(r) - sum(l-1);
    }
} tree;

struct minSegmentTree{
    int tree[8000002], lazy[8000002], maxLoc[8000002];

    void init(int i, int l, int r, int* A){
        if(l==r){
            tree[i] = A[l];
            lazy[i] = 0;
            maxLoc[i] = l;
            return;
        }
        lazy[i] = 0;
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        if(tree[i*2] >= tree[i*2+1]) tree[i] = tree[i*2], maxLoc[i] = maxLoc[i*2];
        else tree[i] = tree[i*2+1], maxLoc[i] = maxLoc[i*2+1];
    }

    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        tree[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, val);
        update(i*2+1, m+1, r, s, e, val);
        if(tree[i*2] >= tree[i*2+1]) tree[i] = tree[i*2], maxLoc[i] = maxLoc[i*2];
        else tree[i] = tree[i*2+1], maxLoc[i] = maxLoc[i*2+1];
    }
} mstree;

int n, k, t;
int arr[2000002];
int lLim[2000002];
int basic;

stack<pair<int, int> > stk;
vector<int> link[2000002];
int par[2000002], depth[2000002], sz[2000002];
int vCount, leafCnt;
vector<int> leaf;
int ans;

int DP[2002][2002];

void dfs(int x, int d = 0){
    if((int)link[x].size() == 0) depth[x] = d;
    else depth[x] = -1e9;
    sz[x] = 1;
    for(auto y: link[x]){
        dfs(y, d+1);
        sz[x] += sz[y];
    }
}

int tmpArr[2002];
void dfs2(int x){
    int currentSize = 1;

    for(auto y: link[x]){
        dfs2(y);
        for(int i=1; i<=currentSize+sz[y]; i++) tmpArr[i] = 0;
        for(int i=0; i<=currentSize; i++){
            for(int j=0; j<=sz[y]; j++){
                if(!i && !j) continue;
                tmpArr[i+j] = max(tmpArr[i+j], DP[x][i] + DP[y][j]);
            }
        }
        currentSize += sz[y];
        for(int i=0; i<=currentSize; i++) DP[x][i] = tmpArr[i];
    }
    for(int i=1; i<=currentSize; i++) DP[x][i]++;
}

int main(){
    scanf("%d %d %d", &n, &k, &t);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        if(arr[i] <= t) lLim[i] = -1;
        else{
            while(!stk.empty() && stk.top().first < i) stk.pop();
            if(stk.empty()) basic++, lLim[i] = -1;
            else lLim[i] = stk.top().second;
        }
        if(arr[i] < t){
            int val = i + (t - arr[i]);
            while(!stk.empty() && stk.top().first <= val) stk.pop();
            stk.push(make_pair(val, i));
        }
    }

    while(!stk.empty()) stk.pop();
    stk.push(make_pair(0, ++vCount));
    for(int i=n; i>=1; i--){
        if(lLim[i] == -1) continue;
        while(stk.top().first > i) stk.pop();
        link[stk.top().second].push_back(++vCount);
        par[vCount] = stk.top().second;
        stk.push(make_pair(lLim[i], vCount));
    }

    for(int i=1; i<=vCount; i++){
        if((int)link[i].size() == 0){
            leafCnt++;
            leaf.push_back(i);
        }
    }
    dfs(1);

    int toCount = min(leafCnt, k);
    tree.init(vCount);
    mstree.init(1, 1, vCount, depth);
    ans = 0;

    dfs2(1);
    ans = max(0, DP[1][toCount] - 1);

//    tree.add(1, 1);
//
//    while(toCount--){
//        int maxLoc = mstree.maxLoc[1];
//        assert(maxLoc != 1);
//
//        mstree.update(1, 1, vCount, maxLoc, maxLoc, -1e9);
//        while(tree.sum(maxLoc, maxLoc) == 0){
//            tree.add(maxLoc, 1);
//            mstree.update(1, 1, vCount, maxLoc, maxLoc+sz[maxLoc]-1, 1);
//            maxLoc = par[maxLoc];
//            ans++;
//        }
//    }

    printf("%d\n", n - (basic + ans));
}

Compilation message

prison.cpp: In function 'int main()':
prison.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%d %d %d", &n, &k, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47252 KB Output is correct
2 Correct 31 ms 48216 KB Output is correct
3 Correct 30 ms 48128 KB Output is correct
4 Correct 27 ms 48308 KB Output is correct
5 Correct 30 ms 48352 KB Output is correct
6 Correct 28 ms 48660 KB Output is correct
7 Correct 28 ms 48576 KB Output is correct
8 Correct 32 ms 48332 KB Output is correct
9 Correct 30 ms 48472 KB Output is correct
10 Correct 31 ms 48400 KB Output is correct
11 Correct 32 ms 48196 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47244 KB Output is correct
2 Runtime error 349 ms 170032 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47252 KB Output is correct
2 Correct 31 ms 48216 KB Output is correct
3 Correct 30 ms 48128 KB Output is correct
4 Correct 27 ms 48308 KB Output is correct
5 Correct 30 ms 48352 KB Output is correct
6 Correct 28 ms 48660 KB Output is correct
7 Correct 28 ms 48576 KB Output is correct
8 Correct 32 ms 48332 KB Output is correct
9 Correct 30 ms 48472 KB Output is correct
10 Correct 31 ms 48400 KB Output is correct
11 Correct 32 ms 48196 KB Output is correct
12 Correct 26 ms 47252 KB Output is correct
13 Correct 27 ms 48180 KB Output is correct
14 Correct 29 ms 48076 KB Output is correct
15 Correct 28 ms 48336 KB Output is correct
16 Correct 28 ms 48432 KB Output is correct
17 Correct 32 ms 48844 KB Output is correct
18 Correct 28 ms 48588 KB Output is correct
19 Correct 28 ms 48284 KB Output is correct
20 Correct 32 ms 48472 KB Output is correct
21 Correct 29 ms 48436 KB Output is correct
22 Correct 29 ms 48204 KB Output is correct
23 Correct 39 ms 57516 KB Output is correct
24 Incorrect 36 ms 55628 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47348 KB Output is correct
2 Runtime error 227 ms 143784 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47252 KB Output is correct
2 Correct 31 ms 48216 KB Output is correct
3 Correct 30 ms 48128 KB Output is correct
4 Correct 27 ms 48308 KB Output is correct
5 Correct 30 ms 48352 KB Output is correct
6 Correct 28 ms 48660 KB Output is correct
7 Correct 28 ms 48576 KB Output is correct
8 Correct 32 ms 48332 KB Output is correct
9 Correct 30 ms 48472 KB Output is correct
10 Correct 31 ms 48400 KB Output is correct
11 Correct 32 ms 48196 KB Output is correct
12 Correct 26 ms 47252 KB Output is correct
13 Correct 27 ms 48180 KB Output is correct
14 Correct 29 ms 48076 KB Output is correct
15 Correct 28 ms 48336 KB Output is correct
16 Correct 28 ms 48432 KB Output is correct
17 Correct 32 ms 48844 KB Output is correct
18 Correct 28 ms 48588 KB Output is correct
19 Correct 28 ms 48284 KB Output is correct
20 Correct 32 ms 48472 KB Output is correct
21 Correct 29 ms 48436 KB Output is correct
22 Correct 29 ms 48204 KB Output is correct
23 Correct 39 ms 57516 KB Output is correct
24 Incorrect 36 ms 55628 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47252 KB Output is correct
2 Correct 31 ms 48216 KB Output is correct
3 Correct 30 ms 48128 KB Output is correct
4 Correct 27 ms 48308 KB Output is correct
5 Correct 30 ms 48352 KB Output is correct
6 Correct 28 ms 48660 KB Output is correct
7 Correct 28 ms 48576 KB Output is correct
8 Correct 32 ms 48332 KB Output is correct
9 Correct 30 ms 48472 KB Output is correct
10 Correct 31 ms 48400 KB Output is correct
11 Correct 32 ms 48196 KB Output is correct
12 Correct 26 ms 47244 KB Output is correct
13 Runtime error 349 ms 170032 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -