제출 #1140867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140867		ray1457	Stove (JOI18_stove)	C++20	50 / 100	142 ms	327680 KiB

stove

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define ll long long

const int INF = 1e9;

void solve() {
    int n,k;
    cin >> n >> k;
    vi a(n+1);
    for (int i = 1; i<=n; i++) cin >> a[i];

    vector<vi> dp(n+1, vi(k+1, INF));
    dp[1][1] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j<=k; j++) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + a[i+1] - a[i]);
            if (j < k)
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1);
        }
    }

    int mn = 1e9;
    for (auto i : dp[n]) mn = min(mn, i);

    cout << mn << endl;

}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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