SHARE
TWEET

Skyline

a guest Feb 27th, 2020 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ALEX ENACHE
  2.  
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. #include <math.h>
  7. #include <iomanip>
  8. #include <bitset>
  9.  
  10. #include <queue>
  11. #include <deque>
  12. #include <stack>
  13.  
  14. #include <map>
  15. #include <unordered_map>
  16. #include <set>
  17. #include <unordered_map>
  18.  
  19. #include <random>
  20. #include <time.h>
  21. #include <assert.h>
  22.  
  23. using namespace std;
  24.  
  25. #include <fstream>
  26. //ifstream cin("input");ofstream cout("output");
  27. ifstream cin("skyline.in");ofstream cout("skyline.out");
  28.  
  29. const int MAXN = 4e4 + 5;
  30. long long h[MAXN], l[MAXN];
  31. int st[MAXN];
  32. int dr[MAXN];
  33. long long sp[MAXN];
  34.  
  35. stack < int > s;
  36.  
  37.  
  38. int main() {
  39.  
  40.     int n;
  41.     cin >> n;
  42.  
  43.     for (int i = 1; i <= n; i++) {
  44.         cin >> h[i] >> l[i];
  45.         sp[i] = sp[i - 1] + l[i];
  46.     }
  47.  
  48.     s.push(0);
  49.     h[0] = -1;
  50.     for (int i = 1; i <= n; i++) {
  51.         while (h[s.top()] >= h[i]) {
  52.             s.pop();
  53.         }
  54.         st[i] = s.top();
  55.         s.push(i);
  56.     }
  57.  
  58.     while (!s.empty()) {
  59.         s.pop();
  60.     }
  61.    
  62.     s.push(n+1);
  63.     h[n+1] = -1;
  64.     for (int i = n; i >= 1; i--) {
  65.         while (h[s.top()] >= h[i]) {
  66.             s.pop();
  67.         }
  68.         dr[i] = s.top();
  69.         s.push(i);
  70.     }
  71.  
  72.  
  73.     long long ans = 0;
  74.  
  75.     for (int i = 1; i <= n; i++) {
  76.         long long now = h[i] * (sp[dr[i] - 1] - sp[st[i]]);
  77.         ans = max(ans, now);
  78.     }
  79.  
  80.     cout << ans << '\n';
  81. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top