text: // Time:  O(n^2) = O(1), since n is at most 99
  // Space: O(n) = O(1)
  
  class Solution {
  public:
      double champagneTower(int poured, int query_row, int query_glass) {
          vector<double> result(1 + query_row);
          result[0] = poured;
          for (int i = 1; i <= query_row; ++i) {
              for(int j = i; j >= 0; --j) {
                  result[j] = max((result[j] - 1), 0.0) / 2 +
                              max((result[j - 1] - 1), 0.0) / 2;
              }
          }
          return min(result[query_glass], 1.0);
      }
  };
  