fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 4 ;
  4. long long mem[5002][5002];
  5. vector<long long > a(N) ;
  6. int n ;
  7. long long dp(int idx,int rem){
  8.     if (idx==n)return 0;
  9.     long long &ret=mem[idx][rem];
  10.     if (~ret)return ret;
  11.     long long op=0;
  12.     if (rem>=idx+1)
  13.         op= max(op, dp(idx,rem-idx-1)+a[idx]);
  14.     op= max(op,dp(idx+1,rem));
  15.     return ret=op;
  16. }
  17. int main() {
  18.     ios_base::sync_with_stdio(),cin.tie(0),cout.tie(0) ;
  19.     cin>>n;
  20.     for (int i = 0; i < n; ++i) {
  21.         cin>>a[i];
  22.     }
  23.     for (int i = 0; i <= n; ++i) {
  24.         for (int j = 0; j <= n; ++j) {
  25.             mem[i][j]=-1;
  26.         }
  27.     }
  28.     cout<<dp(0,n)<<'\n';
  29.     return 0 ;
  30. }
  31.  
Success #stdin #stdout 0s 5244KB
comments (?)
stdin
copy 
5
3 1 1 1 1 1
stdout
copy 
15
https://ideone.com/ifSQ11
language:
C++14 (gcc 8.3)
created:
2 days 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!