Submission #1256362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256362		pasta	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	49 ms	2632 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define pb push_back


const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int n, L[maxn], dp[maxn], h[maxn], w[maxn], ps[maxn];

int mul(int a, int b) {
	return (1ll * a * b) % mod;
}

int C(int a) {
	return 1ll * a * (a + 1) / 2 % mod;
}
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> h[i];
	for (int i = 1; i <= n; i++)
		cin >> w[i];

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

	for (int i = 1; i <= n; i++) {
		ps[i] = ps[i - 1] + w[i];
		ps[i] %= mod;
	}

	ll ans = 0;
	dp[0] = 0;
	// cout << L[1] << '\n';
	for (int i = 1; i <= n; i++) {
		ll ln = (ps[i] - ps[L[i]] + mod) % mod;
		ll l1 = (ln - w[i] + mod) % mod;

		
		dp[i] = dp[L[i]] + mul(ln, C(h[i]));
		dp[i] %= mod;


		ll a = 0;

		a += mul(w[i], mul(C(h[i]), l1));
		a %= mod;
		a += mul(C(w[i]), C(h[i]));
		a %= mod;

		ll b = mul(dp[L[i]], w[i]); 

		ans = ans + a + b;
		ans %= mod;
	}
	// cout << '\n';
	cout << ans << '\n';
}

• 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