Submission #458030

#	Time	Username	Problem	Language	Result	Execution time	Memory
458030		fuad27	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	106 ms	6084 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod (long long)1000000007
ll sum(ll n) {
	return (n*(n+1))/2;
}
ll multiply(ll a, ll b) {
	a%=mod;
	b%=mod;
	return (a*b)%mod;
}
int main () {
	ll n, ans = 0;
	cin >> n;
	ll h[n+1] = {0}, w[n+1] = {0}, pref[n+1] = {0}, dp[n+1] = {0};
	for(int i = 1;i<=n;i++) {
			cin >> h[i];
	}
	for(int i = 1;i<=n;i++) {
		cin >> w[i];
	}
	for(int i = 1;i<=n;i++) {
		pref[i] = pref[i-1]+w[i];	
	}
	stack<ll> s;
	s.push(0);
	for(int i = 1;i<=n;i++) {
		while(!s.empty() and h[s.top()] >= h[i])s.pop();
		dp[i] = dp[s.top()]+multiply(sum(h[i]), (pref[i] - pref[s.top()]));
		ans += multiply(dp[s.top()], w[i]) + multiply(sum(h[i]), multiply(pref[i-1] - pref[s.top()], w[i]))+multiply(sum(h[i]), sum(w[i]));
		dp[i]%=mod;
		ans%=mod;s.push(i);
	}
	cout<<ans;
}

• 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