YEZAELP

SMMR-104: Potion

Jul 31st, 2021
602
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const int N = 1e6 + 10;
  6. const int INF = 1e18;
  7. lli dp[2][14];
  8. lli ar[N];
  9. int n;
  10.  
  11. int main(){
  12.  
  13.     scanf("%d", &n);
  14.  
  15.     for(int i=1;i<=n;i++) scanf("%lld", &ar[i]);
  16.  
  17.     if(n < 4){
  18.         printf("GGWP");
  19.         return 0;
  20.     }
  21.  
  22.     for(int j=0;j<=4;j++)
  23.         dp[0][j] = dp[1][j] = -INF;
  24.  
  25.     for(int i=0;i<=n;i++) dp[i][0] = 0;
  26.  
  27.     for(int i=1;i<=n;i++){
  28.         int cur = i % 2;
  29.         int pre = (i - 1) % 2;
  30.         for(int j=1;j<=4;j++){
  31.             lli a, b;
  32.             if(j % 2 == 1) a = dp[pre][j-1] - ar[i];
  33.             else a = dp[pre][j-1] + ar[i];
  34.             b = dp[pre][j];
  35.             dp[cur][j] = max(a, b);
  36.         }
  37.         for(int j=1;j<=4;j++)
  38.             dp[pre][j] = -INF;
  39.     }
  40.  
  41.     lli mx = -INF;
  42.     for(int i=1;i<=n;i++)
  43.         mx = max(mx, dp[i % 2][4]);
  44.  
  45.     printf("%lld\n", mx);
  46.  
  47.     return 0;
  48. }
RAW Paste Data