제출 #1310503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310503		marcogambaro	The short shank; Redemption (BOI21_prison)	C++20	100 / 100	213 ms	49412 KiB

prison

#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define readv(v) do { for(auto &i: v) cin >> i; } while(0)
#define writev(v) do { for(auto i: v) cout << i << " "; } while(0)
#define _ << " " <<
#define ll long long
#define u64 unsigned long long
#ifndef MARCO
bool dbg = 0;
#define info(str, ...)
#define infon(str, ...)
#else
bool dbg = 1;
#define info(str, ...) do { fprintf(stderr, "\033[31m" str "\033[0m", ##__VA_ARGS__); } while(0)
#define infon(str, ...) do { fprintf(stderr, "\033[31m" str "\033[0m\n", ##__VA_ARGS__); } while(0)
#endif
constexpr int LOG = 30;

#define int long long

signed main(){	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);   
    
    int N, d, T; cin >> N >> d >> T;
	vector<int> V(N);
	readv(V);
    
    stack<int> rebels, mt;
	vector<int> pw(N+1);
	pw[N] = -1;

	int reb = N;

	for(int i=0; i<N; i++) {
		rebels.push(i);
		mt.push(i);

		while(!rebels.empty() && i - rebels.top() + V[rebels.top()] > T) {
			rebels.pop();
			int p = mt.top();
			mt.pop();

			if(!mt.empty() && pw[mt.top()] < pw[p]){
				mt.pop();
				mt.push(p);
			}
		}
		if(rebels.empty()) {
			reb--;
			continue;
		}

		pw[mt.top()]++;
	}

	infon("pw ...");
	for(int i: pw) info("%d ", i); infon("");
	infon("reb = %d", reb);

	sort(rall(pw));
	for(int i=0; i<d; i++) reb -= max((ll)0, pw[i]-1);

	cout << reb << "\n";
}

/*
11 10 10
1 9 11 11 11 11 11 11 11 11 11
*/

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