Submission #1237496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237496		thuhienne	Stove (JOI18_stove)	C++20	50 / 100	1096 ms	876 KiB

stove

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

#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int t;cin >> t;while (t--) solve();
#define rf(__abc__) freopen(__abc__".inp","r",stdin);freopen(__abc__".out","w",stdout);

const int mod = 1e9 + 7;

long long pw(long long x,long long y) {
    if (y == 0) return 1;
    if (y % 2 == 0) {
        long long a = pw(x,y/2);
        return a*a%mod;
    } else {
        long long a = pw(x,y - 1);
        return a*x%mod;
    }
}

int add(int x,int y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
}

int subtract(int x,int y) {
    x -= y;
    if (x < 0) x += mod;
    return x;
}

int mul(long long x,int y) {
    x *= y;
    if (x >= mod) x %= mod;
    return x;
}

///Code goes here
int n,k;
int arr[100009],dp[100009];
int main() {
    //rf("");
    FastIO
    //MULTEST
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> arr[i];
    sort(arr + 1,arr + 1 + n);
    for (int i = 0;i <= k;i++) dp[i] = 1e9 + 10;
    dp[1] = 1;
    for (int i = 2;i <= n;i++) {
        for (int j = k;j >= 1;j--) {
            dp[j] = min(dp[j - 1] + 1,dp[j] + arr[i] - arr[i - 1]);
        }
    }
    cout << *min_element(dp + 1,dp + 1 + k);
    return 0;
}

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