oj.uz

Submission #1103027

# Submission time Handle Problem Language Result Execution time Memory
1103027 2024-10-19T12:14:16 Z VerdantGMD Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 2 ms 6876 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6484 KB Output is correct
2 Incorrect 1 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6484 KB Output is correct
2 Incorrect 2 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6484 KB Output is correct
2 Incorrect 1 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6648 KB Output is correct
2 Incorrect 2 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6484 KB Output is correct
2 Incorrect 1 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -