Submission #914411

#	Time	Username	Problem	Language	Result	Execution time	Memory
914411		Aiperiii	Stove (JOI18_stove)	C++14	0 / 100	1 ms	4444 KiB

stove

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=5e3+5;
int dp[N][N],x[N][N];
signed main(){
    int n,k;
    cin>>n>>k;
    vector <int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        dp[0][i]=a[i]+1-a[0];
        if(i-1>=0 && i+1<n)x[0][i]=min(x[0][i-1],dp[0][i]-a[i+1]);
        else if(i==0 && i+1<n)x[0][i]=dp[0][i]-a[i+1];
    }
    for(int i=1;i<k;i++){
        for(int j=0;j<n;j++){
            if(j-1>=0)dp[i][j]=a[j]+1+x[i-1][j-1];
            if(j-1>=0 && j+1<n)x[i][j]=min(x[i][j-1],dp[i][j]-a[j+1]);
            else if(j==0 && j+1<n)x[i][j]=dp[i][j]-a[j+1];
        }
    }
    cout<<dp[k-1][n-1];
}

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