Submission #1344140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344140		Jakub_Wozniak	The short shank; Redemption (BOI21_prison)	C++20	15 / 100	16 ms	652 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;
vector<vector<int>> dp;
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];



    dp.resize(n+5);
    for(int i = 0 ; i <= n+3 ; i++)dp[i].resize(D+3);


    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 = T+12314;
            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