Fshl0

Untitled

Jan 8th, 2022
1,110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. //#define mp make_pair
  5. #define pb push_back
  6. #define loop(i,x,y) for(int i=x;i<=y;i++)
  7.  
  8. using namespace std;
  9. typedef long long ll;
  10.  
  11. const int N = 5e3 + 9;
  12. const int MOD = 1e9 + 7;
  13. const int INF = 1e9 + 1;
  14.  
  15. int prefixSum[N], dp[N][N], A[N], prevOdd[N], nextOdd[N], segTree[2][N][4*N];
  16.  
  17. int main () {
  18.     int n, firstOdd = -1, lastOdd = -1;
  19.     cin >> n;
  20.    
  21.     for (int i = 1; i <= n; i++) {
  22.         cin >> A[i];
  23.         prefixSum[i] = prefixSum[i - 1] + A[i];
  24.     }
  25.    
  26.     int last = 0;
  27.     for (int i = 1; i <= n; i++) {
  28.         if (last)
  29.             prevOdd[i] = last;
  30.         else prevOdd[i] = 0;
  31.        
  32.         if (A[i] & 1) {
  33.             last = i;
  34.            
  35.             if (firstOdd == -1)
  36.                 firstOdd = i;
  37.         }
  38.     }
  39.    
  40.     last = 0;
  41.     for (int i = n; i >= 1; i--) {
  42.         if (last)
  43.             nextOdd[i] = last;
  44.         else nextOdd[i] = n + 1;
  45.        
  46.         if (A[i] & 1) {
  47.             last = i;
  48.            
  49.             if (lastOdd == -1)
  50.                 lastOdd = i;
  51.         }
  52.     }
  53.    
  54.     dp[1][n] = prefixSum[n];
  55.    
  56.     for (int len = n - 1; len >= 1; len--) {
  57.         for (int l = 1; l + len - 1 <= n; l++) {
  58.             int r = l + len - 1;
  59.            
  60.             if (r >= lastOdd && l <= firstOdd) {
  61.                 dp[l][r] = prefixSum[r] - prefixSum[l - 1];
  62.                
  63.                 continue;
  64.             }
  65.            
  66.             int bestBelowFloor = -INF;
  67.            
  68.             if (r < lastOdd) {
  69.                 for (int k = nextOdd[r]; k <= nextOdd[nextOdd[r]] - 1; k++)
  70.                     bestBelowFloor = max (bestBelowFloor, dp[l][k]);
  71.             }
  72.            
  73.             if (l > firstOdd) {
  74.                 for (int k = prevOdd[prevOdd[l]] + 1; k <= prevOdd[l]; k++)
  75.                     bestBelowFloor = max (bestBelowFloor, dp[k][r]);
  76.             }
  77.            
  78.             dp[l][r] = prefixSum[r] - prefixSum[l - 1] + bestBelowFloor;
  79.         }
  80.     }
  81.    
  82.     int res = -INF;
  83.     for (int l = 1; l <= n; l++) {
  84.         int c = 0;
  85.         for (int r = l; r <= n; r++) {
  86.             if (A[r] & 1)
  87.                 c++;
  88.                
  89.             if (((prefixSum[r] - prefixSum[l - 1]) & 1) && c == 1)
  90.                 res = max (res, dp[l][r]);
  91.         }
  92.     }
  93.    
  94.     if (res == -INF)
  95.         cout << -1 << "\n";
  96.     else cout << res << "\n";
  97.    
  98.     return 0;
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment