Submission #1134527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134527		ezzzay	K blocks (IZhO14_blocks)	C++20	53 / 100	37 ms	71052 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3000;
int dp[N][N];
int a[N];
signed main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++)dp[i][j]=1e9;
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            int mx=0;
            for(int p=j+1;p<=i;p++)mx=max(mx,a[p]);
            for(int p=1;p<=k;p++){
                dp[i][p]=min(dp[i][p],dp[j][p-1]+mx);
               // cout<<mx<<endl;
            }
        }
    }
    cout<<dp[n][k];
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47