fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. using namespace std;
  4. const int maxn=(int)3e3+2;
  5. ll pre_sum[maxn];
  6. int n,k;
  7. ll dp[302][302][302];
  8. ll calc(int l,int r,int k)
  9. {
  10.     if(k==0) return 0;
  11.     if(dp[l][r][k]!=-1) return dp[l][r][k];
  12.     ll &res=dp[l][r][k];
  13.     for(int i=l;i<r;++i)
  14.     {
  15.         ll val=(pre_sum[i]-pre_sum[l-1])*(pre_sum[r]-pre_sum[i]);
  16.         for(int j=0;j<k;++j)
  17.         {
  18.             res=max(res,calc(l,i,j)+calc(i+1,r,k-1-j)+val);
  19.         }
  20.     }
  21.     return res; 
  22.  
  23. }
  24. int main()
  25. {
  26.     freopen("DIVPART.INP","r",stdin);
  27.     freopen("DIVPART.OUT","w",stdout);
  28.     ios_base::sync_with_stdio(0);cin.tie(0);
  29.     cin>>n>>k;
  30.     for(int i=1;i<=n;++i)
  31.     {
  32.         int x;
  33.         cin>>x;
  34.         pre_sum[i]=pre_sum[i-1]+x; 
  35.     }
  36.     if(n<=3e2) 
  37.     {
  38.         for(int i=1;i<=n;++i) for(int j=i;j<=n;++j)
  39.         for(int x=1;x<=k;++x) dp[i][j][x]=-1;
  40.         cout<<calc(1,n,k);
  41.     }
  42.     return 0; 
  43. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BhZR99
language:
C++ (gcc 8.3)
created:
15 hours 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!