fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define precision(n)   cout << setprecision(n) << fixed
  9. #define sf(a)          scanf("%d",&a)
  10. #define sf2(a,b)       scanf("%d %d",&a,&b)
  11. #define sf3(a,b,c)     scanf("%d%d%d",&a,&b,&c)
  12. #define pi             acos(-1.0)
  13. #define eps            0.0000000001
  14. #define gl(a)          scanf("%llu",&a)
  15. #define mod            1000000007
  16. #define pf             printf
  17. #define loop(ds,itr)   for ( auto itr = ds.begin(); itr != ds.end(); itr++ )
  18. #define fr(i,n)        for ( int i = 0; i < n; i++ )
  19. #define check(x)       cout << x << endl;
  20. #define bug            cout << 'x' << endl;
  21. #define srt(n)         (int)(sqrt(double(n))+eps)
  22. #define e              2.71828182845
  23. #define mp             make_pair
  24. #define min4(a,b,c,d)  min(a,min(b,min(c,d)));
  25. #define power(n,i)     (int)(pow(n,i)+eps)
  26. #define inf            0x3f3f3f3f
  27. #define MAX            100005
  28. #define ff             first
  29. #define ss             second
  30. #define all(v)         v.begin(),v.end()
  31.  
  32. #ifdef FACT
  33.      #include <ctime>
  34.      clock_t tStart = clock();
  35.      #define debug(args...) {dbg,args; cerr<<endl;}
  36.      #define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
  37.      #define bug printf("%d\n",__LINE__);
  38.  
  39. #else
  40.     #define debug(args...)
  41.     #define timeStamp
  42.  
  43. #endif
  44.  
  45. struct debugger{
  46.     template<typename T> debugger & operator , (const T& v){
  47.         cerr<<v<<" ";
  48.         return *this;
  49.     }
  50. }dbg;
  51.  
  52.  
  53. typedef long long ll;
  54. typedef unsigned long long ull;
  55. typedef pair < int,int > ii;
  56. typedef priority_queue< int,vector<int>, greater<int> > pq_increasing;
  57. typedef tree< int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
  58. template < class T > inline T gcd(T a, T b){while(b){a%=b;swap(a,b);}return a;}
  59.  
  60. const int sz = 5015;
  61. int n,k;
  62. ll arr[sz];
  63. ll dp[sz][sz];
  64.  
  65. ll solve ( int idx , int k ) {
  66.     if ( idx == n ) {
  67.         return -1e18;
  68.     }
  69.     if ( dp[idx][k] != -1 ) return dp[idx][k];
  70.     ll ans = arr[idx];
  71.     if ( arr[idx] >= 0 ) ans = max(ans, solve(idx+1,k) + arr[idx] );
  72.     else {
  73.         if ( k > 0 ) ans = max(0LL,solve(idx+1,k-1) );
  74.         else ans = max(ans,arr[idx]);
  75.     }
  76.     return dp[idx][k] = ans;
  77. }
  78.  
  79. int main () {
  80.     ///freopen("input.txt","r",stdin);
  81.     ///freopen("output.txt","w",stdout);
  82.     ios_base::sync_with_stdio(false);
  83.  
  84.     int t;
  85.     sf(t);
  86.     for ( int T = 1; T <= t; T++ ) {
  87.         memset(dp,-1,sizeof(dp));
  88.         sf2(n,k);
  89.         fr(i,n) scanf("%lld",&arr[i]);
  90.         ll mxm = arr[0];
  91.         fr(i,n) {
  92.             mxm = max(mxm,solve(i,k));
  93.         }
  94.         printf("Case %d: %lld\n",T,mxm);
  95.  
  96.  
  97.     }
  98.  
  99.  
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0.11s 200112KB
comments (?)
stdin
copy 
4
3 1
-8 -9 -1
3 0
-8 -1 -9
3
1 2 3
8 1
1 5 -7 5 0 -10 5 2
stdout
copy 
Case 1: 0
Case 2: -1
Case 3: 13
Case 4: 5
https://ideone.com/LL9XUk
language:
C++14 (gcc 8.3)
created:
4 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!