Submission #487659

#	Time	Username	Problem	Language	Result	Execution time	Memory
487659		stefantaga	Stove (JOI18_stove)	C++14	50 / 100	36 ms	47620 KiB

stove

#include <bits/stdc++.h>

using namespace std;
long long din[5005][5005];
long long mini,v[5005];
int n,k,i,j;
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>k;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        din[1][i]=v[i]-v[1]+1;
    }
    for (i=2;i<=k;i++)
    {
        mini=1e18;
        for (j=i;j<=n;j++)
        {
            mini=min(mini,din[i-1][j-1]-v[j]);
            din[i][j]=v[j]+mini+1;
        }
    }
    cout<<din[k][n]<<'\n';
    return 0;
}

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