제출 #1184439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184439		kl0989e	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	422 ms	589824 KiB

prison

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,d,t;
    cin >> n >> d >> t;
    vi a(n);
	int cnt=0;
    for (int i=0; i<n; i++) {
        cin >> a[i];
		if (a[i]<=t) {
			cnt++;
		}
    }
	vector<vector<vi>> dp(n+1,vector<vi>(n+1,vi(d+1,1e9)));
	dp[0][0][0]=0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<=n; j++) {
			for (int k=0; k<=d; k++) {
				int jj=max(j,min(n,i+t-a[i]+1));
				dp[i+1][jj][k]=min(dp[i+1][jj][k],dp[i][j][k]+(j>i && a[i]>t));
				if (k<d) {
					dp[i][j][k+1]=min(dp[i][j][k+1],dp[i][j][k]);
				}
				if (k<d && a[i]>t) {
					dp[i+1][0][k+1]=min(dp[i+1][0][k+1],dp[i][j][k]);
				}
			}
		}
	}
	int ans=n;
	for (int j=0; j<=n; j++) {
		ans=min(ans,dp[n][j][d]);
	}
	cout << ans+cnt << '\n';
    return 0;
}

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