Advertisement
ismaeil

D. Maximum Sum on Even Positions

Jun 25th, 2020
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. #define INF 4e18
  5.  
  6. const int N = 2e5 + 10;
  7. ll Memo[N][3][2];
  8. int n ,a[N];
  9.  
  10. ll calc(int i ,int tk ,bool flag){
  11.     if( i == n ){
  12.         if( tk == 1 )
  13.             if( flag )
  14.                 return -INF;
  15.         return 0;
  16.     }
  17.  
  18.     ll &Re = Memo[i][tk][flag];
  19.     if( Re != -1ll ) return Re;
  20.  
  21.     ll Res = 0ll;
  22.     if( tk == 0 ) {
  23.         Res = calc(i + 1 ,0 ,0) + (i % 2 == 0) * a[i];
  24.         Res = max(Res ,calc(i + 1 ,1 ,1) + (i % 2 == 1) * a[i]);
  25.     } else if( tk == 1 ) {
  26.         Res = calc(i + 1 ,1 ,!flag) + (i % 2 == 1) * a[i];
  27.         if( flag == 0 ) /// --- \EvenLenOfRev --- ///
  28.             Res = max(Res ,calc(i + 1 ,2 ,flag) + (i % 2 == 0) * a[i]);
  29.     } else if( tk == 2 )
  30.         Res = calc(i + 1 ,2 ,flag) + (i % 2 == 0) * a[i];
  31.  
  32.     return Re = Res;
  33. }
  34.  
  35. void Solve() {
  36.     scanf("%d" ,&n);
  37.     for(int i=0 ; i<n ; i++)
  38.         scanf("%d" ,&a[i]);
  39.  
  40.     for(int i=0 ; i<n ; i++)
  41.         for(int j=0 ; j<3 ; j++)
  42.             for(int k=0 ; k<2 ; k++)
  43.                 Memo[i][j][k] = -1ll;
  44.  
  45.     ll Ans = calc(0 ,0 ,0);
  46.     printf("%I64d\n" ,Ans);
  47. }
  48.  
  49. int main() {
  50.     int Tc; scanf("%d" ,&Tc);
  51.     while( Tc-- ) Solve();
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement