fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. int sum(int a[101],int st,int en)
  5. {
  6.     ll sum=0;
  7.     for(int i=st;i<=en;++i)
  8.     sum+=a[i];
  9.     sum%=100;
  10.     return sum;
  11. }
  12. main()
  13. {  // freopen("in.txt","r",stdin);
  14.     int a[101],j,n,t;
  15.     ll m[101][101],q;
  16.     //ios_base::sync_with_stdio(0);
  17.     while(scanf("%d",&n)!=-1)//scanf("%d",&n)!=NULL)
  18.     {
  19.         for(int i=0;i<n;++i)
  20.         scanf("%d",&a[i]);
  21.         //cin>>a[i];
  22.         for(int i=1;i<=n;++i)
  23.         m[i][i]=0;
  24.         for(int l=2;l<=n;++l)
  25.         {
  26.             for(int i=0;i<=n-l;++i)
  27.             {//cout<<"h";
  28.                 j=i+l-1;
  29.                 m[i+1][j+1]=INT_MAX;
  30.                 for(int k=i;k<=j;++k)
  31.                 {
  32.                    // cout<<sum(a,i,k)<<" "<<sum(a,k+1,j)<<"f ";
  33.                     q=m[i+1][k+1]+m[k+2][j+1]+sum(a,i,k)*sum(a,k+1,j);
  34.                     m[i+1][j+1]=min(q,m[i+1][j+1]);
  35.                 }
  36.             }
  37.         }
  38.         /* for(int i=1;i<=n;++i)
  39.         {
  40.             for(int j=1;j<=n;++j)
  41.             cout<<m[i][j]<<" ";
  42.             cout<<endl;
  43.         }*/
  44.         printf("%lld\n",m[1][n]);
  45.         //cout<<m[1][n]<<endl;
  46.     }
  47. }
  48.  
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
2
18 19
3
20 40 60
stdout
copy 
342
2400
https://ideone.com/W7Oz40
language:
C++ (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!