Submission #1043201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043201		0pt1mus23	K blocks (IZhO14_blocks)	C++14	53 / 100	1040 ms	40032 KiB

blocks

#pragma GCC optimize("O3", "inline")

#include <bits/stdc++.h> 
using namespace std; 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define ins insert
#define pb push_back
// #define int long long int
#define pii pair<int, int>
#define endl '\n' 
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash z0hashp
#define div  z0dvp
const int mod = 1e9 +7, sze = 1e5 +23, inf = INT_MAX, P = 1453;
int dp[sze][101];

int arr[sze];

void opt1z(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];

    }
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int  j=1;j<=k;j++){
            int mx = arr[i];
            for(int ip=i-1;ip>=0;ip--){
                dp[i][j]=min(dp[i][j],dp[ip][j-1] + mx);
                // cout<<i<<" "<<j<<" "<<ip<<" "<<mx<<endl;
                mx=max(mx,arr[ip]);
            }

        }
    }

    drop(dp[n][k]);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
} 
 

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