mickypinata

SMMR-T158: Quick Maths

Aug 4th, 2021
636
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. typedef long long lli;
  5.  
  6. enum status {
  7.     MIN, MAX
  8. };
  9.  
  10. const int N = 500;
  11.  
  12. int arr[N + 1];
  13. char opr[N + 1];
  14. lli dp[N + 1][N + 1][2];
  15.  
  16. int main(){
  17.  
  18.     int nArr;
  19.     scanf("%d", &nArr);
  20.     for(int i = 1; i < nArr; ++i){
  21.         scanf("%d %c", &arr[i], &opr[i]);
  22.     }
  23.     scanf("%d", &arr[nArr]);
  24.     for(int i = 1; i <= nArr; ++i){
  25.         dp[i][i][MIN] = arr[i];
  26.         dp[i][i][MAX] = arr[i];
  27.     }
  28.     for(int d = 2; d <= nArr; ++d){
  29.         for(int l = 1; l <= nArr - d + 1; ++l){
  30.             int r = l + d - 1;
  31.             lli ansMax = -1e18;
  32.             lli ansMin = 1e18;
  33.             for(int i = l; i < r; ++i){
  34.                 if(opr[i] == '+'){
  35.                     ansMax = max(ansMax, dp[l][i][MAX] + dp[i + 1][r][MAX]);
  36.                     ansMin = min(ansMin, dp[l][i][MIN] + dp[i + 1][r][MIN]);
  37.                 } else if(opr[i] == '-'){
  38.                     ansMax = max(ansMax, dp[l][i][MAX] - dp[i + 1][r][MIN]);
  39.                     ansMin = min(ansMin, dp[l][i][MIN] - dp[i + 1][r][MAX]);
  40.                 }
  41.             }
  42.             dp[l][r][MAX] = ansMax;
  43.             dp[l][r][MIN] = ansMin;
  44.         }
  45.     }
  46.     cout << dp[1][nArr][MIN] << ' ' << dp[1][nArr][MAX];
  47.  
  48.     return 0;
  49. }
  50.  
RAW Paste Data