fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int calWater(vector<int> &buildingHeights) {
  6.     if(buildingHeights.empty()) return 0;
  7.     int n = buildingHeights.size();
  8.     vector<int> leftMax(n), rightMax(n);
  9.     leftMax[0] = buildingHeights[0];
  10.     for(int i=1; i<n; i++) {
  11.         leftMax[i] = max(leftMax[i-1], buildingHeights[i]);
  12.     }
  13.     rightMax[n-1] = buildingHeights[n-1];
  14.     for(int i=n-2; i>=0; i--) {
  15.         rightMax[i] = max(rightMax[i+1], buildingHeights[i]);
  16.     }
  17.     int ans = 0;
  18.     for(int i=1; i<n-1; i++) {
  19.         int curr = min(leftMax[i-1], rightMax[i+1]);
  20.         ans += max(0, curr - buildingHeights[i]);
  21.     }
  22.     return ans;
  23. }
  24.  
  25. int main() {
  26. 	int n;
  27. 	cin >> n;
  28. 	vector<int> v;
  29. 	for(int i=0; i<n; i++) {
  30. 		int var;
  31. 		cin >> var;
  32. 		v.push_back(var);
  33. 	}
  34. 	cout << calWater(v) << "\n";
  35. 	return 0;
  36. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
7
0 6 0 8 6 0 10
stdout
copy 
16
https://ideone.com/1BKGm1
language:
C++ (gcc 8.3)
created:
4 years 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!