fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int trapWater(vector<int>& heights) {
  5.     int heightsSize = heights.size();
  6.     int totalWater = 0;
  7.  
  8.     // Array to store the maximum heights to the left and right of each position
  9.     vector<int> maximumLeft(heightsSize);
  10.     vector<int> maximumRight(heightsSize);
  11.  
  12.     // Precompute the maximum heights to the left of each position
  13.     maximumLeft[0] = heights[0];
  14.     for(int i = 1; i < heightsSize; i++) {
  15.         maximumLeft[i] = max(maximumLeft[i-1], heights[i]);
  16.     }
  17.  
  18.     // Precompute the maximum heights to the right of each position
  19.     maximumRight[0] = heights[heightsSize - 1];
  20.     for(int i = heightsSize - 2; i >= 0; i--) {
  21.         maximumRight[i] = max(maximumRight[i+1], heights[i]);
  22.     }
  23.  
  24.     // Calculate the trapped water at each position
  25.     for(int i = 0; i < heightsSize; i++) {
  26.         totalWater += max(0, min(maximumLeft[i], maximumRight[i]) - heights[i]);
  27.     }
  28.  
  29.     return totalWater;
  30. }
  31.  
  32. int main() {
  33. 	int n; cin >> n;
  34. 	vector<int> heights(n);
  35. 	for(int& height : heights) cin >> height;
  36. 	cout << trapWater(heights);
  37.  
  38. 	return 0;
  39. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
12
0 1 0 2 1 0 1 3 2 1 2 1
stdout
copy 
6
https://ideone.com/LDdvLl
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!