Submission #538256

#	Time	Username	Problem	Language	Result	Execution time	Memory
538256		Stickfish	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2066 ms	185952 KiB

prison

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 2e6 + 123;
vector<int> edg[MAXN];
int rt[MAXN];

int init(int n) {
    int t;
    cin >> t;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<pair<int, int>> stck;
    vector<int> vl(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        stck.push_back({a[i], i});
        while (stck.size() && t - stck.back().first < i - stck.back().second)
            stck.pop_back();
        if (stck.size()) {
            vl[i] = stck.back().second;
        } else {
            ++ans;
            vl[i] = n + 1;
        }
    }
    //for (int i = 0; i < n; ++i)
        //cout << vl[i] << ' ';
    //cout << endl;
    vector<int> way;
    for (int i = n - 1; i >= 0; --i) {
        while (way.size() && vl[way.back()] > i) {
            way.pop_back();
        }
        if (vl[i] >= i) {
            rt[i] = -1;
            continue;
        }
        if (vl[i] < i && way.size()) {
            rt[i] = way.back();
            edg[way.back()].push_back(i);
        } else {
            rt[i] = 0;
            edg[0].push_back(i);
        }
        way.push_back(i);
    }
    //for (int i = 0; i < n; ++i) {
        //cout << rt[i] << ' ';
    //}
    //cout << endl;
    return ans;
}

vector<int> unite(vector<int> a, vector<int> b, int d) {
    int n = a.size();
    int m = b.size();
    vector<int> ans(min(d + 1, n + m - 1));
    for (int i = 0; i < n && i <= d; ++i) {
        for (int j = 0; j < m && i + j <= d; ++j) {
            ans[i + j] = max(ans[i + j], a[i] + b[j]);
        }
    }
    return ans;
}

vector<int> dfs(int v, int d) {
    if (edg[v].empty()) {
        return {0, 1};
    }
    vector<int> ans = {0};
    for (auto u : edg[v]) {
        ans = unite(ans, dfs(u, d), d);
    }
    for (int i = 1; i < ans.size(); ++i)
        ++ans[i];
    //cout << v << ": ";
    //for (auto x : ans)
        //cout << x << ' ';
    //cout << endl;
    return ans;
}

signed main() {
    int n, d;
    cin >> n >> d;
    int neut = init(n);
    int ans = dfs(0, d).back();
    //cout << "(" << ans << ' ' << neut << ") " << endl;
    cout << n - ans - neut + 1 << endl;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<int> dfs(int, int)':
prison.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 1; i < ans.size(); ++i)
      |                     ~~^~~~~~~~~~~~

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