fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <map>
  4. #include <iomanip>
  5. #include <set>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <queue>
  9. #include <cctype>
  10. #include <cstring>
  11. #include <algorithm>
  12. using namespace std;
  13.  
  14. typedef pair<int, int> pii;
  15. typedef vector<int> vi;
  16. typedef vector< pii > vii;
  17.  
  18. #define INF 2e9
  19.  
  20. long long n, nums[500500], dp[500500][2][3];
  21.  
  22. long long best(int numsLeft, int beenTaking, int arrLeft) {
  23.     if (arrLeft < 0 || numsLeft < 0) return 0;
  24.  
  25.     if (dp[numsLeft][beenTaking][arrLeft] != -1)
  26.         return dp[numsLeft][beenTaking][arrLeft];
  27.  
  28.     if (beenTaking) {
  29.         // continue Taking
  30.         long long c1 = best(numsLeft - 1, beenTaking, arrLeft) + nums[numsLeft];
  31.         // stop Taking
  32.         long long c2 = best(numsLeft - 1, 0, arrLeft);
  33.  
  34.         return dp[numsLeft][beenTaking][arrLeft] = max(c1, c2);
  35.     } else {
  36.         // continue not Taking
  37.         long long c1 = best(numsLeft - 1, beenTaking, arrLeft);
  38.         // start Taking
  39.         long long c2 = best(numsLeft - 1, 1, arrLeft - 1) + nums[numsLeft];
  40.  
  41.         return dp[numsLeft][beenTaking][arrLeft] = max(c1,c2);
  42.     }
  43. }
  44.  
  45. int main() {
  46.     //freopen("in.txt", "r", stdin);
  47.  
  48.     memset(dp, -1, sizeof(dp));
  49.  
  50.     cin >> n;
  51.     for (int i = 0; i < n; i++) {
  52.         cin >> nums[i];
  53.     }
  54.  
  55.     cout << best(n - 1, 0, 2) << endl;
  56.  
  57.     return 0;
  58. }
  59.  
  60.  
Success #stdin #stdout 0.02s 30832KB
comments (?)
stdin
copy 
5
5 3 -20 4 8
stdout
copy 
20
https://ideone.com/P5PB7h
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!