Submission #1256358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256358		pasta	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1 ms	328 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 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.empty() && 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 x = ps[i] - ps[L[i]] + mod;
		x %= mod;
		
		dp[i] = dp[L[i]] + 1ll * C(h[i] + 1) * x % mod;
		ans = ans + 1ll * x % mod * dp[L[i]] % mod;
		ans %= mod;
		ans = ans + 1ll * C(h[i] + 1) * C(x + 1) % mod;
		ans %= mod;
		dp[i] %= mod;
		// cout << dp[i] << ' ';
	}
	// cout << '\n';
	cout << ans << '\n';
}

• 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