Submission #1344139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344139		Jakub_Wozniak	The short shank; Redemption (BOI21_prison)	C++20	15 / 100	17 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 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++)
    {
        for(int i = n ; i >= 1 ; i--)
        {
            dp[i][d] = maxn*10+124;
            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++;
                dp[i][d] = min(dp[i][d] , dp[j][d-1] + COST);
            }

        }
    }

    cout << dp[1][D+1] << '\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