제출 #1258584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258584		njoop	Fancy Fence (CEOI20_fancyfence)	C++20	30 / 100	15 ms	4424 KiB

fancyfence

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, h[100010], w[100010], p[100010], mod=1e9+7, pos, val, ans;
stack<pair<int, int>> s;

int mul(int x) {
    return (x*(x+1)/2)%mod;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> h[i];
    }
    for(int i=1; i<=n; i++) {
        cin >> w[i];
        p[i] = p[i-1] + w[i];
    }
    s.push({0, 0});
    for(int i=1; i<=n; i++) {
        ans += pos*w[i];
        ans %= mod;
        ans += mul(w[i])*mul(h[i]);
        ans %= mod;
        while(s.top().second >= h[i]) {
            int cp = s.top().first, ch = s.top().second;
            s.pop();
            int t = (cp-s.top().first+mod)%mod;
            pos -= t*mul(ch);
            pos %= mod;
            if(pos < 0) pos += mod;
        }
        pos += ((p[i]-s.top().first+mod)%mod)*mul(h[i]);
        pos %= mod;
        s.push({p[i], h[i]});
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27