fork download 
  1. #include <bits/stdc++.h>
  2. #define For(i,a,b) for(int i=a; i<=b; i++)
  3. #define Forn(i,a,b) for(int i = a; i>=b; i--)
  4. #define F first
  5. #define S second
  6. #define ll long long
  7. #define pii pair<int,int>
  8. #define pil pair<int, long long>
  9. #define pli pair<long long,int>
  10. #define pll pair<long long, long long>
  11. #define PB push_back
  12. #define mp make_pair
  13. #define bit(x , i) ((x >> i) & 1 )
  14. #define CNT(x) __builtin_popcountll(x)
  15. using namespace std;
  16. int const N = 2005 ;
  17. int n, m, a[N],sz ;
  18. ll ans = 1e17 + 5, sum, sumbl[N], cnt[N];
  19. ll f[N][N] ;
  20. void sub3()
  21. {
  22.     for(int i = 1 ; i <= n ; i++)
  23.         sumbl[i] = sumbl[i - 1] + a[i] ;
  24.     memset(f, 0x3f, sizeof f) ;
  25.     for(int i = 1 ; i <= n ; i++)
  26.         f[i][1] = sumbl[i] * i ;
  27.     for(int x = 2 ; x <= m ; x++)
  28.         for(int i = x ; i <= n ; i++)
  29.             for(int j = 1 ; j <= i / x ; j++)
  30.                 f[i][x] = min(f[i][x], f[i - j][x - 1] + (sumbl[i] - sumbl[i - j]) * j);
  31.     cout << f[n][m] ;
  32. }
  33. int main()
  34. {
  35.     ios_base :: sync_with_stdio(false);
  36.     cin.tie(0);
  37.     cout.tie(0);
  38.     freopen("AQUARIUM.INP","r",stdin);
  39.     freopen("AQUARIUM.OUT","w",stdout);
  40.     cin >> n >> m ;
  41.     for(int i = 1 ; i <= n ; i++)
  42.         cin >> a[i] ;
  43.     sort(a + 1, a + 1 + n) ;
  44.  
  45.         sub3() ;
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 35232KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/UIG7PJ
language:
C++14 (gcc 8.3)
created:
7 days 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!