fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 3e4 + 7;
  5. int maxLeft[N] = {}, maxRight[N] = {};
  6.  
  7. int trapWater(vector<int>& heights) {
  8.     int heightsSize = heights.size();
  9.     int totalWater = 0; // Variable to store the total trapped water
  10.  
  11. 	maxLeft[0] = heights[0];
  12. 	maxRight[heightsSize - 1] = heights[heightsSize - 1];
  13. 	for (int i = 1; i < heightsSize; i++)
  14. 		maxLeft[i] = max(maxLeft[i - 1], heights[i]);
  15. 	for (int i = heightsSize - 2; i >= 0; i--)
  16. 		maxRight[i] = max(maxRight[i + 1], heights[i]);
  17.  
  18.     for(int i = 0; i < heightsSize; i++) {
  19.  
  20.         // Calculate the trapped water at the current position
  21.         totalWater += min(maxLeft[i], maxRight[i]) - heights[i];
  22.     }
  23.  
  24.     return totalWater;
  25. }
  26.  
  27. int main() {
  28. 	int n; cin >> n;
  29. 	vector<int> heights(n);
  30. 	for(int& height : heights) cin >> height;
  31. 	cout << trapWater(heights);
  32.  
  33. 	return 0;
  34. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
12
0 1 0 2 1 0 1 3 2 1 2 1
stdout
copy 
6
https://ideone.com/vyW4w9
language:
C++ (gcc 8.3)
created:
4 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!