fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<fstream>
  3.  
  4. using namespace std;
  5. #define MP      make_pair
  6. #define PB      push_back
  7. #define PF      push_front
  8. #define F       first
  9. #define S       second
  10. #define EPS     1e-9
  11. #define MOD 1000000007
  12. #define pi 3.14159265
  13.  
  14. typedef vector<int> VI;
  15. typedef vector<VI> VVI;
  16. typedef pair<int,int> PII;
  17. typedef  long long int lli;
  18. typedef unsigned long long int ULL;
  19. #define endl '\n'
  20. #define ip(n) scanf("%d",&n)
  21. #define For(i,s,n) for(i=s;i<n;i++)
  22. #define SYNC ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(NULL);
  23. // Useful hardware instructions
  24. #define bitcount                    __builtin_popcount
  25. #define gcd                         __gcd
  26. #define INF 99999999
  27. #define SIZ 1010000
  28. lli dp[5100][550],can[SIZ],n;
  29. lli calc(int i,int sl,lli val,int ctr){
  30.     //cout<<i<<" "<<val<<" "<<endl;
  31.     if(i<n-1 && !sl)return INF;
  32.     if(i == n-1)return val*can[i]*(ctr+1);
  33.     if(dp[i][sl])return dp[i][sl];
  34.     dp[i][sl] = INF;
  35.  
  36.     dp[i][sl] = min(calc(i+1,sl-1,1,0)+ val*can[i]*(ctr+1), calc(i+1,sl,val*can[i],ctr+1) );
  37.     cout<<i<<" "<<sl<<" "<<dp[i][sl]<<endl;
  38.     return dp[i][sl];
  39. }
  40.  
  41. int main()
  42. {
  43.     SYNC;
  44.     int i,x,y,k;
  45.     cin>>n>>k;
  46.     for(i=0;i<n;i++)cin>>can[i];
  47.     cout<<calc(0,k,1,0)<<endl;
  48.  //   cout<<cnt<<endl;
  49. }
  50.  
Success #stdin #stdout 0s 45856KB
comments (?)
stdin
copy 
5 2
5
2
3
7
1
stdout
copy 
3 2 841
3 1 8
2 2 98
2 1 8
1 2 28
1 1 8
0 2 13
13
https://ideone.com/aWTLb2
language:
C++ (gcc 8.3)
created:
7 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!