mickypinata

SMMR-T104: Potion

Aug 5th, 2021
724
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e6;
  5.  
  6. int arr[N + 1], dp[N + 2][5];
  7.  
  8. int main(){
  9.  
  10.     int nArr;
  11.     scanf("%d", &nArr);
  12.     if(nArr < 4){
  13.         cout << "GGWP";
  14.         return 0;
  15.     }
  16.     for(int i = 1; i <= nArr; ++i){
  17.         scanf("%d", &arr[i]);
  18.     }
  19.     for(int c = 0; c < 4; ++c){
  20.         dp[nArr + 1][c] = -1e9;
  21.     }
  22.     for(int i = 1; i <= nArr + 1; ++i){
  23.         dp[i][4] = 0;
  24.     }
  25.     for(int i = nArr; i >= 1; --i){
  26.         for(int c = 3; c >= 0; --c){
  27.             if(c % 2 == 0){
  28.                 dp[i][c] = max(dp[i + 1][c], dp[i + 1][c + 1] - arr[i]);
  29.             } else {
  30.                 dp[i][c] = max(dp[i + 1][c], dp[i + 1][c + 1] + arr[i]);
  31.             }
  32.         }
  33.     }
  34.     cout << dp[1][0];
  35.  
  36.     return 0;
  37. }
  38.  
RAW Paste Data