fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4LSaTG
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!