Submission #1056677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056677		Piokemon	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	38 ms	9576 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 500;
int koszt[N+9][N+9];
int dp[N+9][N+9];
int a[N+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,t;
    cin >> n >> d >> t;
    for (int x=1;x<=n;x++){
        cin >> a[x];
    }
    for (int x=1;x<=n;x++){
        int val=0;
        int pop=1e9;
        for (int y=x;y<=n;y++){
            pop = min(a[y],pop+1);
            if (pop<=t)val++;
            koszt[x][y]=val;
        }
    }
    for (int x=0;x<=n+1;x++){
        for (int y=0;y<=d+1;y++)dp[x][y]=1e9;
    }
    dp[1][0]=0;
    for (int x=1;x<=n;x++){
        for (int k=0;k<=d;k++){
            for (int y=x+1;y<=n+1;y++){
                dp[y][k+1]=min(dp[y][k+1],dp[x][k]+koszt[x][y-1]);
            }
        }
    }
    cout << dp[n+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