Advertisement
FEgor04

Untitled

Jul 13th, 2020
893
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef vector<ll> vi;
  5. #define watch(x) cout << #x << " is " << x << endl
  6. const int INF = 2e9+1;
  7. #define int long long
  8. typedef pair<int, int> pii;
  9.  
  10. signed main() {
  11.     int n;
  12.     cin >> n;
  13.     vi a(n+2, -INF);
  14.     vi al(n+2);
  15.     vi ar(n+2);
  16.     vi pref(n+2, 0);
  17.     vi w(n);
  18.     for(int i = 1; i <= n; i++) {
  19.         cin >> w[i-1];
  20.         cin >> a[i];
  21.     }
  22.     for(int i = 1; i <= n; i++) {
  23.         pref[i] = pref[i-1] + w[i-1];
  24.     }
  25.     vector<int> st;
  26.     st.push_back(0);
  27.     for (int i = 1; i < n + 2; ++i) {
  28.         while (a[st.back()] > a[i]) {
  29.             ar[st.back()] = i;
  30.             st.pop_back();
  31.         }
  32.         st.push_back(i);
  33.     }
  34.     st.clear();
  35.     st.push_back(0);
  36.     for (int i = n+1; i >= 1; --i) {
  37.         while (a[st.back()] > a[i]) {
  38.             al[st.back()] = i;
  39.             st.pop_back();
  40.         }
  41.         st.push_back(i);
  42.     }
  43.     int answ = 0;
  44.     for(int i = 1; i <= n; i++) {
  45.         answ = max(answ, a[i] * (pref[ar[i]-1] - pref[al[i]]));
  46.     }
  47.     cout << answ;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement