Submission #1293103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293103		nerrrmin	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	2 ms	584 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 = w[i];
        while(g.back().first > h[i])
        {
            sumaw += g.back().second;
            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) * ((sumaw + 1) * (sumaw) / 2);
            ans %= mod;
            g.pop_back();
        }
        g.pb(make_pair(h[i], sumaw ));
    }
    cout << ans << endl;
    return 0;
}

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