제출 #1344155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1344155		Jakub_Wozniak	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	18 ms	1604 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define st first
#define nd second
const ll maxn = 500+9;
int dp[maxn][maxn];
int t[maxn];
int opt[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n , D , T;
    cin >> n >> D >> T;
    for(int i = 1; i<= n ;i++)cin >> t[i];


    for(int i = 1; i <= n ; i++)dp[i][0] = maxn*123+15;
    for(int d = 1 ; d <= D+1 ; d++)
    {
        opt[n+1] = n+1;
        for(int i = n ; i >= 1 ; i--)
        {
            dp[i][d] = 1+dp[i+1][d-1]; // stawiam granice zaraz przy mnie
            opt[i] = i+1;
            

            int COST = 0;
            int Pop = (1e+9)+7;
            for(int j = i+1 ; j <= n+1 ; j++)
            {
                Pop++;
                Pop = min(Pop,t[j-1]);
                if(Pop <= T)COST++;
                if(j == opt[i+1])
                {
                    if(dp[i][d] > dp[j][d-1]+ COST)opt[i] = j;
                    dp[i][d] = min(dp[i][d] , dp[j][d-1] + COST);
                }
            }

        }
    }

    cout << dp[1][D+1] << '\n';

    return 0;
}

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