Submission #888969

#	Time	Username	Problem	Language	Result	Execution time	Memory
888969		Deaddog	Stove (JOI18_stove)	C++17	50 / 100	141 ms	262144 KiB

stove

#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF =1e9;
signed main()
{
    int n, k;
    cin >> n >> k;
    vector <int> x(n);
    for(int i=0; i<n;i++)
    {
        cin >> x[i];
    }
    sort(x.begin(), x.end());
    vector<vector<int>>dp(n, vector<int>(k+1, INF));
    for(int i=0;i<n;i++)
    {
        dp[i][0] = INF;
    }
    dp[0][1] = 1;
    for(int i=1; i<n;i++)
    {
        for(int j=1;j<=k&&j<=i+1;j++)
        {
            dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+x[i]-x[i-1]);
        }
    }
    cout << dp[n-1][k];
    return 0;
}

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