fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3.  
  4. const int MAX_N = 8000, MAX_G = 800;
  5. const long long INF = 1ll<<62;
  6. int N,G;
  7. long long s[MAX_N+10];
  8. struct {long long val; int opt;} dp[MAX_N+10][MAX_G+10];
  9.  
  10. inline long long cost(int l, int r) { return (s[r]-s[l-1])*1ll*(r-l+1); }
  11.  
  12. int main()
  13. {
  14.     scanf("%d%d\n", &N, &G);
  15.     for (int i = 1; i <= N; ++i)
  16.     {
  17.         scanf("%d\n", s+i);
  18.         s[i] += s[i-1];
  19.     }
  20.     if (N <= G)
  21.     {
  22.         printf("%lld", s[N]);
  23.         return 0;
  24.     }
  25.  
  26.     for (int i = 1; i <= N; ++i)
  27.     {
  28.         dp[i][i].val = s[i];
  29.         dp[i][i].opt = std::max(i-1, 1);
  30.  
  31.         dp[i][1].val = i*s[i];
  32.         dp[i][1].opt = 1;
  33.     }
  34.  
  35.     for (int i = 2; i <= N; ++i)
  36.         for (int j = std::min(G, i-1); j > 1 ; --j)
  37.         {
  38.             dp[i][j].val = INF;
  39.  
  40.             int to = j==G?i-1:dp[i][j+1].opt;
  41.             for (int k = dp[i-1][j].opt; k <= to; ++k)
  42.             {
  43.                 long long val = dp[k][j-1].val + cost(k+1, i);
  44.                 if (dp[i][j].val > val)
  45.                 {
  46.                     dp[i][j].val = val;
  47.                     dp[i][j].opt = k;
  48.                 }
  49.             }
  50.         }
  51.  
  52.     printf("%lld", dp[N][G].val);
  53. }
Success #stdin #stdout 0s 79552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i8ALbd
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!