fork download
  1. #include <iostream>
  2. #include <algorithm>
  3. #define endl '\n'
  4.  
  5. using namespace std;
  6.  
  7. const int N = 511;
  8. const int K = 329;
  9. const long long INF = 1e18;
  10.  
  11. int n,k;
  12. long long a[N],sum[N];
  13. bool used[N][K];
  14. long long state[N][K];
  15.  
  16. long long recurse(int pos, int blocks) {
  17. if(pos>n) {
  18. if(blocks==0) return 0;
  19. else return INF;
  20. }
  21. if(blocks==0) return INF;
  22. if(used[pos][blocks]) return state[pos][blocks];
  23. int i;
  24. long long ans = INF, curr, curr_sum, rem_sum;
  25. for(i=pos;i<=n;i++) {
  26. curr_sum=sum[i]-sum[pos-1];
  27. rem_sum=sum[n]-sum[i];
  28. curr=(k-1)*curr_sum*curr_sum-2*curr_sum*(rem_sum)+recurse(i+1,blocks-1);
  29. ans=min(ans,curr);
  30. }
  31.  
  32. used[pos][blocks]=true;
  33. state[pos][blocks]=ans;
  34.  
  35. return ans;
  36. }
  37.  
  38. int main() {
  39. ios_base::sync_with_stdio(false);
  40. cin.tie(NULL);
  41. int i;
  42.  
  43. cin>>n>>k;
  44. for(i=1;i<=n;i++) {
  45. cin>>a[i];
  46. sum[i]=a[i]+sum[i-1];
  47. }
  48.  
  49. cout<<recurse(1,k)<<endl;
  50.  
  51. return 0;
  52. }
  53.  
Success #stdin #stdout 0s 4760KB
stdin
Standard input is empty
stdout
0