Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define all(x) x.begin(),x.end()
- #define pb push_back
- #define fr first
- #define sc second
- #define mp make_pair
- #define int long long
- const int maxn = 1e4+10;
- const int maxk = 3e3+10;
- const int inf = 1e18+10;
- int n, k, a[maxn], dp[maxn][maxk];
- void solve() {
- cin >> n >> k;
- for(int i = 1; i <= n; i++) cin >> a[i];
- sort(a+1,a+1+n,greater<int>());
- dp[1][0] = 0;
- for(int j = 1; j <= k; j++) dp[1][j] = inf;
- for(int i = 2; i <= n; i++) {
- for(int j = 0; j <= k; j++) {
- if(3*j > i) dp[i][j] = inf;
- else {
- dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
- }
- }
- }
- cout << dp[n][k] << endl;
- }
- int32_t main() {
- ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- //freopen("in.in","r",stdin);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement