Submission #1241894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241894		khanhtt	Stove (JOI18_stove)	C++20	20 / 100	1100 ms	196544 KiB

stove

#include <iostream>
#include <cstring>
using namespace std;
int n,k,A[100005];
long long f[5005][5005];
long long dp(int i, int l){
    if (l>k) return 1e9+5;
    if (i>n) return 0;
    if (f[i][l]!=-1) return f[i][l];
    f[i][l]=1e9+5;
    for (int j=i; j<=n; j++){
        f[i][l]=min(f[i][l],dp(j+1, l+1)+(A[j]-A[i]+1));
    }
    return f[i][l];
}
main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    memset(f,-1,sizeof(f));
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> A[i];
    if (k>=n){
        cout << n;
    }
    else{
        cout << dp(1,0);
    }
}

Compilation message (stderr)

stove.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50