Submission #1219037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219037		duongquanghai08	Fancy Fence (CEOI20_fancyfence)	C++20	28 / 100	15 ms	3928 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+ 5;
const long long inv2 = 500000004; // Correct
const int MOD = 1e9 + 7;
long long h[N], w[N], prefix[N], dp[N];
int n;
int l[N];

void Solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    
    // Revert to storing true prefix sums
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        prefix[i] = prefix[i - 1] + w[i];
    }

    long long ans = 0;
    stack<int> st;
    for(int i = 1; i <= n; i++) {
        while(!st.empty() && h[st.top()] >= h[i]) st.pop();
        if(st.empty()) l[i] = 0;
        else l[i] = st.top();
        st.push(i);

        // Calculate W from true sums. This is simpler and safer
        // since (prefix[i-1] - prefix[l[i]]) will be non-negative if all w[i] are >= 0.
        // To be fully robust for negative widths, you could do:
        long long W = (prefix[i - 1] - prefix[l[i]]);
        W = (W % MOD + MOD) % MOD;

        // The rest of your logic remains the same
        ans = (ans + h[i] * (h[i] + 1) % MOD * inv2 % MOD * w[i] % MOD * (w[i] + 1) % MOD * inv2 % MOD) % MOD;
        ans = (ans + h[i] * (h[i] + 1) % MOD * inv2 % MOD * w[i] % MOD * W % MOD) % MOD;
        
        long long current_dp_term = h[i] * (h[i] + 1) % MOD * inv2 % MOD * (W + (w[i] % MOD) + MOD) % MOD;
        
        dp[i] = (current_dp_term + dp[l[i]]) % MOD;
        
        ans = (ans + w[i] % MOD * h[l[i]] % MOD * dp[l[i]] % MOD + MOD) % MOD;
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
}

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