Submission #1212834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212834		eggx50000	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	23 ms	47184 KiB

prison

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
using ll = long long;

int n, d, to, k[2000099], ret, c;
vector <int> g[2000099], vvv;

struct Da{
    int u, v;
};
stack <Da> stk, tr;

int dfs(int node){
    int ma = 0;
    for(int &e : g[node]){
        int nv = dfs(e);
        if(nv < ma) vvv.push_back(nv);
        else{
            vvv.push_back(ma);
            ma = nv;
        }
    }
    return ma + 1;
}

int main()
{
    scanf("%d %d %d", &n, &d, &to);
    for(int i = 1; i <= n; i ++){
        scanf("%d", k + i);
        stk.push({i, k[i]});
        while(stk.size() && stk.top().v + i - stk.top().u > to) stk.pop();
        if(stk.size() == 0) ret ++;
        else if(stk.top().u < i){
            Da tt = stk.top();
            int ni = ++c;
            while(tr.size() && tr.top().v <= tt.u + 1){
                g[c].push_back(tr.top().u);
                tr.pop();
            }
            tr.push({c, tt.u + 1});
        }
    }
    while(tr.size()){
        vvv.push_back(dfs(tr.top().u));
        tr.pop();
    }
    sort(vvv.begin(), vvv.end());
    reverse(vvv.begin(), vvv.end());
    for(int i = 0; i < d; i ++){
        if(i >= vvv.size()) continue;
        ret += vvv[i];
    }
    printf("%d", n - ret);
    return 0;
}

Compilation message (stderr)

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

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