제출 #1293184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293184		nerrrmin	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	84 ms	4924 KiB

fancyfence

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 10;
long long n, h[maxn], w[maxn];
long long pref[maxn];

int main()
{
    cin >> n;
    for (long long i = 1; i <= n; ++ i)
        cin >> h[i];
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> w[i];
        pref[i] += w[i];
    }
    w[n+1] = 0;
    h[n+1] = 0;
    vector < pair < long long /*visochina*/, long long/*long longerval*/ > > g;
    g.pb(make_pair(0, 0));
    long long ans = 0, mod = 1e9+7;
    for (long long i = 1; i <= n + 1; ++ i)
    {
        long long sumaw = 0;
        while(g.back().first > h[i])
        {
            sumaw += g.back().second;
            sumaw %= mod;
            long long currh = g.back().first;
            long long currw = g.back().second;
           // cout << currh << ", " << currw << endl;
            long long sz  = g.size();
            long long pre = g[sz-2].first;
            long long limit = max(pre, h[i]);
            long long diffh = currh - limit;


            //cout << sumaw << " " << diffh << endl;
            ans += (((diffh) * (diffh+1)/2 + diffh * limit) % mod) * (((sumaw + 1) * (sumaw) / 2) % mod);
            ans %= mod;
            g.pop_back();
        }
        sumaw += w[i];
        sumaw %= mod;
        g.pb(make_pair(h[i], sumaw ));
    }
    cout << ans << endl;
    return 0;
}

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