Submission #1103027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103027		VerdantGMD	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	2 ms	6876 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll tab[1000005];
ll h[1000005];
ll w[1000005];
ll dp[1000005];
ll mod = 1e9+7;
ll notdp[1000005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }

    dp[1] = ((((h[1] * (h[1]+1))%mod)/2) * w[1]) % mod;
    vector<pair<ll, ll>> v;
    v.push_back({0, 0});
    v.push_back({h[1], 1});

    for(int i = 2; i <= n; i++)
    {
        ll temp = w[i];
        notdp[i] = ((((h[i] * (h[i]+1))%mod)/2) * ((w[i] * (w[i]+1))%mod)/2 ) % mod;
        notdp[i] = (notdp[i] - (((h[i] * (h[i]+1))%mod)/2 * w[i])%mod + mod) % mod;

        while(v.back().first > h[i])
        {
            w[i] += w[v.back().second];
            v.pop_back();
        }

        ll inbig = ((((h[i] * (h[i]+1))%mod)/2) * ((w[i] * (w[i]+1))%mod)/2 ) % mod;
        inbig = (inbig - (((h[i] * (h[i]+1))%mod)/2 * w[i]) % mod + mod) % mod;
        inbig = (inbig - notdp[i] + mod) % mod;
        notdp[i] = (notdp[i] + inbig) % mod;
        ll fromdp = (dp[v.back().second] * temp) % mod;
        fromdp = (fromdp - dp[v.back().second] + mod) % mod;
        notdp[i] = (notdp[i] + fromdp) % mod;

        dp[i] = dp[v.back().second];

        dp[i] = (dp[i] + ((((h[i] * (h[i]+1))%mod)/2) * w[i]) % mod ) % mod;
        v.push_back({h[i], i});
    }
    ll wyn = 0;
    for(int i = 1; i <= n; i++)
    {
        wyn = (wyn + dp[i] + notdp[i]) % mod;
        //cout << dp[i] << " " << notdp[i] << endl;
    }
    cout << wyn << endl;

}

• 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