0 like 0 dislike
2,531 views

edited | 2,531 views

0 like 0 dislike
```#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
ll dp[5005][5005] ;
ll diff[500000+5];

ll kk(ll y,ll g){

ll vv = 0 ;
vv = abs(diff[g] - diff[y]);
return vv ;

}

int main() {

ll n ;
cin>>n ;
ll k;
cin>>k ;
ll b[n+1] = {0};
ll i = 1 ;
while(i<=n){
cin>>b[i] ;
i++;
}

ll p1 = n/k ;//....g
ll p2 = n/k + 1 ; //...g+1...
ll k2 = 0 ;//count of g..basically x..
ll k5 = 0 ; //count of g+1...basically y..
i = 1 ;
while(i<=k) {
ll vv = (n-i)/k ;
vv++;
if(vv==p1){
k2++;
}
if(vv==p2){
k5++;
}
i++;
}
cout<<k2<<" "<<k5 ;
cout<<"\n";

sort(b+1,b+n+1);

i = 2 ;
while(i<=n){
ll gg = abs(b[i]-b[i-1]);
diff[i] = diff[i-1] + gg ;//diff is p-s[]
i++;
}

i = 1 ;
while(i<=k2){

ll sum = i*p1 + 0*p2;
ll g = sum ;
ll y = (sum - p1 + 1 );

dp[i][0] = dp[i-1][0] + kk(y,g); //base_case...

i++;
}

i = 1 ;
while(i<=k5){

ll sum = 0*p1 + i*p2;
ll g = sum ;
ll y = (sum - p2 + 1);

dp[0][i] = dp[0][i-1] + kk(y,g); //base_case...

i++;
}

i = 0 ;
while(i<=k2){
ll j = 0 ;
while(j<=k5){

ll sum = i*p1 + j*p2 ;

if(sum!=0){
ll v5 = 1e18 ;
if(j>=1){
//focus on j part....

ll g = sum ;
ll y = (sum - p2 + 1 );
v5 = dp[i][j-1] + kk(y,g);
}
ll v8 = 1e18 ;

if(i>=1){

ll g = sum ;
ll y = (sum - p1 + 1 );
v8 = dp[i-1][j] + kk(y,g);

}

dp[i][j] = min(v5,v8);

}

j++;
}
i++;
}

cout<<dp[k2][k5];

/*

15 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

5
-5 -5 3 3 3

*/

return 0 ;
}```
by Expert (113,040 points)
0 like 0 dislike

Problem Q go through this  :

by Expert (113,040 points)