fork download 
  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 ll long long
  9. #define uint unsigned int
  10. #define ull  unsigned long long
  11. #define pb push_back
  12. #define mk make_pair
  13. #define ins insert
  14. #define all(x) (x).begin(), (x).end()
  15. #define rall(x) (x).rbegin(),(x).rend()
  16. #define X first
  17. #define Y second
  18. #define umap unordered_map
  19. #define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  20. #define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
  21. #define mset multiset
  22. #define pqueue priority_queue
  23.  
  24. template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  25.  
  26. const int  N = 1e5 + 314;
  27. const int INF = 1e9;
  28. const double PI = acos(-1);
  29. const int MOD = 1e9 + 7;
  30. const double eps = 1e-9;
  31. const long long LINF = 1e18 + 3141;
  32. int n;
  33. int a[N];
  34. int dps[70][N];
  35. int dpp[70][N];
  36. void solve(){
  37.     cin >> n;
  38.     for(int i = 1; i <= n; ++i)
  39.         cin >> a[i]; 
  40.     for(int i = a[n]; i <= 30; ++i) {
  41.         dps[i + 30][n] = max(a[n], 0); 
  42.     }    
  43.     for(int i = n - 1; i >= 1; --i) {
  44.  
  45.         for(int j = a[i]; j <= 30 ; ++j) {
  46.             // <= j
  47.             int mx = 0;
  48.             for(int k = -30; k <= j; k++) {
  49.                 mx = :: max(dps[k + 30][i + 1], mx);
  50.             }
  51.             dps[j + 30][i] = max(0, a[i] + mx) ;
  52.         }
  53.     }
  54.  
  55.     for(int i = a[1]; i <= 30; ++i) {
  56.         dpp[i + 30][1] = max(a[1], 0); 
  57.     }
  58.     for(int i = 2; i <= n; ++i) {
  59.         for(int j = a[i]; j <= 30 ; ++j) {
  60.             // <= j
  61.             int mx = 0;
  62.             for(int k = -30; k <= j; k++) {
  63.                 mx = :: max(dpp[k + 30][i - 1], mx);
  64.             }
  65.             dpp[j + 30][i] = max(0, a[i] + mx) ;
  66.         }
  67.     }
  68.     int ans = 0;
  69.     for(int i = 1; i <= n; ++i) {
  70.         ans = max(ans, dpp[a[i] + 30][i - 1] + dps[a[i] + 30][i + 1]);
  71.     }
  72.     cout << ans;
  73.  
  74. }
  75.  
  76. int main(){
  77.     speed();
  78.     int t = 1;
  79.     // cin >> t;
  80.     while(t--)solve();
  81. }
Success #stdin #stdout 0s 4276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wPZS3p
language:
C++ (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!