Submission #936686

#	Time	Username	Problem	Language	Result	Execution time	Memory
936686		Halym2007	Fancy Fence (CEOI20_fancyfence)	C++17	73 / 100	68 ms	1972 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
ll h[N], w[N], sum, mod = 1e9 + 7, n, jog, ans;

ll jogap (ll x, ll y) {
	ll a1 = (x * (x + 1)) / 2;
	a1 %= mod;
	ll a2 = y;
	ll a3 = y + 1;
	if (a2 % 2 == 0) a2 /= 2;
	else a3 /= 2;
	a2 %= mod;a3 %= mod;
	a2 *= a3;
	a2 %= mod;
	a1 *= a2;
	a1 %= mod;
	return a1;
}

ll md(ll x){
	return x % mod;
}

int main () {
//	freopen ("input.txt", "r", stdin);
	bool subtask4 = 0, subtask2 = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
		if (i > 1 and h[i] != h[i - 1]) {
			subtask4 = 1;
		} 
		if (h[i] > 2) subtask2 = 1;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		sum += w[i];
	}
	if (n <= 1000) {
		for (int i = 1; i <= n; ++i) {
			jog += jogap (h[i], w[i]);
			jog = md (jog);
			ll mn = h[i];
			for (int j = i - 1; j > 0; j--) {
				ll sum1 = w[i] + w[j];
				mn = min (mn, h[j]);
				ll ans = jogap (mn, sum1) - jogap (mn, w[j]) - jogap (mn, w[i]);
				while (ans < 0) ans += mod;
				jog += ans;
				jog = md (jog);
			}
		}
	}
	else if (!subtask2) {
		ll sum1 = 0;
		for (int i = 1; i <= n; ++i) {
			if(h[i] == 1) {
				if(sum1 > 0) {
					ans = jogap (2, sum1) - jogap(1, sum1);
					while (ans < 0) ans += mod;
					jog += ans;
					jog = md(jog);
				}
				sum1 = 0;
			}
			else {
				sum1 += w[i];
			}
		}
		if(sum1 > 0){
			ans = jogap (2, sum1) - jogap(1, sum1);
			while (ans < 0) ans += mod;
			jog += ans;
			jog = md(jog);
		}
		jog += jogap(1,sum);
		jog = md(jog);
	}
	else if (!subtask4) {
		jog = jogap (h[1], sum);
	}
	else {
		for (int i = 1; i <= n; ++i) {
			ans = jogap (h[i], sum) - jogap (h[i], sum - w[i]);
			while (ans < 0) ans += mod;
			jog += ans;
			jog %= mod;
			sum -= w[i];
		}
	}
	cout << jog;
}

• 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: 0 / 27