Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef vector<ll> vi;
- #define watch(x) cout << #x << " is " << x << endl
- const int INF = 2e9+1;
- #define int long long
- typedef pair<int, int> pii;
- signed main() {
- int n;
- cin >> n;
- vi a(n+2, -INF);
- vi al(n+2);
- vi ar(n+2);
- vi pref(n+2, 0);
- vi w(n);
- for(int i = 1; i <= n; i++) {
- cin >> w[i-1];
- cin >> a[i];
- }
- for(int i = 1; i <= n; i++) {
- pref[i] = pref[i-1] + w[i-1];
- }
- vector<int> st;
- st.push_back(0);
- for (int i = 1; i < n + 2; ++i) {
- while (a[st.back()] > a[i]) {
- ar[st.back()] = i;
- st.pop_back();
- }
- st.push_back(i);
- }
- st.clear();
- st.push_back(0);
- for (int i = n+1; i >= 1; --i) {
- while (a[st.back()] > a[i]) {
- al[st.back()] = i;
- st.pop_back();
- }
- st.push_back(i);
- }
- int answ = 0;
- for(int i = 1; i <= n; i++) {
- answ = max(answ, a[i] * (pref[ar[i]-1] - pref[al[i]]));
- }
- cout << answ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement