제출 #1190021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190021		tamyte	The short shank; Redemption (BOI21_prison)	C++20	55 / 100	557 ms	589824 KiB

prison

#include <bits/stdc++.h>
 
using namespace std;
struct RMQ {
    int n;
    vector<int> tree, lz;
    RMQ(int n) {
    	this->n = n;
    	tree = vector<int>(4 * n + 1, 0);
    	lz = vector<int>(4 * n + 1, 0);
    }
    void push(int i) {
    	tree[i * 2] += lz[i];
    	tree[i * 2 + 1] += lz[i];
    	lz[i * 2] += lz[i];
    	lz[i * 2 + 1] += lz[i];
    	lz[i] = 0;
    }
    void update(int i, int l, int r, int ql, int qr, int val) {
    	if (ql <= l && r <= qr) {
    		tree[i] += val;
    		lz[i] += val;
    		return;
    	}
    	if (ql > r || qr < l) return;
    	push(i);
    	int m = (l + r) / 2;
    	update(i * 2, l, m, ql, qr, val);
    	update(i * 2 + 1, m + 1, r, ql, qr, val);
    	tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
    }
    void update(int ql, int qr, int val) {
    	update(1, 1, n, ql, qr, val);
    }
    int query(int i, int l, int r, int ql, int qr) {
    	if (ql <= l && r <= qr) {
    		return tree[i];
    	}
    	if (ql > r || qr < l) return n + 1;
    	push(i);
    	int m = (l + r) / 2;
    	return min(query(i * 2, l, m, ql, qr), 
    	query(i * 2 + 1, m + 1, r, ql, qr));
    }
    int query(int ql, int qr) {
    	return query(1, 1, n, ql, qr);
    }
};
 
 
int main() {
    int n, d, t;
    cin >> n >> d >> t;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    d = min(d, n);
    vector<int> left(n + 1, -1);
    stack<int> st;
    for (int i = 1; i <= n; ++i) {
    	while (st.size() && st.top() + t - a[st.top()] < i) {
    		st.pop();
    	}
    	if (st.size()) {
    		left[i] = st.top();
    	}
    	if (a[i] <= t) {
    		left[i] = i;
    		st.push(i);
    	}
    }
    // for (int i = 1; i <= n; ++i) {
    	// cout << left[i] << " ";
    // }
    // cout << endl;
    // cout << endl;
    vector<vector<int>> dp(n + 1, vector<int>(d + 1));
    for (int i = 1; i <= n; ++i) {
    	dp[i][0] = dp[i - 1][0] + (left[i] != -1);
    }
    for (int j = 1; j <= d; ++j) {
    	RMQ seg(n);
    	for (int i = 1; i <= n; ++i) {
    		seg.update(i, i, dp[i - 1][j - 1]);
    		if (left[i] != -1) seg.update(1, left[i], 1);
    		dp[i][j] = seg.query(1, i);
    		// cout << "NOW = ";
    		// for (int k = 1; k <= n; ++k) {
    			// cout << seg.query(k, k) << " ";
    		// }
    		// cout << endl;
    	}
    }
    // for (int j = 0; j <= d; ++j) {
    	// for (int i = 1; i <= n; ++i) {
    		// cout << dp[i][j] << " ";
    	// }
    	// cout << endl;
    // }
    cout << dp[n][d] << endl;
}

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