Submission #67547482

---

Source Code Expand

/*
Original Python code:
import sys
import numpy as np

n, m = map(int, input().split())
if n == m:
    print(0)
    sys.exit()
l = sorted(list(map(int, input().split())))
d = np.zeros(n, dtype=int)
for i in range(n):
    if i == 0:
        d[i] = 0
    else:
        d[i] = l[i] - l[i-1]
dp = np.full(m, -1, dtype=int)
dp[0] = 0
for i in d:
    if i == 0:
        continue
    new_dp = np.full(m, dp[0] + i+1, dtype=int)
    for j in range(m):
        if dp[j] == -1:
            break
        new_dp[j] = min(new_dp[j], dp[j] + i)
        if(j+1 < m):
            new_dp[j+1] = min(new_dp[j+1], dp[j])
    dp = new_dp
print(dp[-1])
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    if (n == m) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> l(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    sort(l.begin(), l.end());
    
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            d[i] = 0;
        } else {
            d[i] = l[i] - l[i-1];
        }
    }
    
    vector<int> dp(m, -1);
    dp[0] = 0;
    
    // Python's "for i in d:" iterates over values, not indices
    for (int idx = 0; idx < n; idx++) {
        int i = d[idx];  // i is the value from array d
        if (i == 0) {
            continue;
        }
        
        vector<int> new_dp(m, dp[0] + i + 1);
        for (int j = 0; j < m; j++) {
            if (dp[j] == -1) {
                break;
            }
            new_dp[j] = min(new_dp[j], dp[j] + i);
            if (j + 1 < m) {
                new_dp[j+1] = min(new_dp[j+1], dp[j]);
            }
        }
        dp = new_dp;
    }
    
    cout << dp[m-1] << endl;
    
    return 0;
} 

Submission Info

Judge Result