Submission #1003426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003426		vjudge1	Flooding Wall (BOI24_wall)	C++17	58 / 100	2306 ms	6224 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10000;
const int MOD = 1e9 + 7;

int dpLft[MAX], dpRght[MAX];
long long lft[MAX];

long long binpow(int a, int b){
	if(!b) return 1;
	long long x = binpow(a, b / 2); x = (x * x) % MOD;
	if(b%2) return (x * a) % MOD;
	else return x;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	vector<int> a(N);
	for(auto &i : a) cin >> i;
	vector<int> b(N);
	for(auto &i : b) cin >> i;
	for(int i = 0; i < N; i++){
		if(a[i] > b[i]) swap(a[i], b[i]);
	}
	if(N <= MAX){
		for(int i = 0; i < N; i++){
			dpLft[i] = 0; dpRght[i] = 0; lft[i] = 2ll;
		}
		vector<pair<int, int>> v(2*N);
		for(int i = 0; i < N; i++){
			v[2*i] = {a[i], i};
			v[2*i+1] = {b[i], i};
		}
		sort(v.begin(), v.end());
		reverse(v.begin(), v.end());
		long long ans = 0;
		vector<int> totalWater(N);
		for(pair<int, int> pr : v){
			int x = pr.first; int i = pr.second;
			// cout << "x "<< x << " i "<< i << "\n";
			long long ways = 1;
			for(int j = 0; j < i; j++){
				ways = (ways * lft[j]) % MOD;
			}
			for(int j = i+1; j < N; j++){
				long long w = (ways * dpRght[j]) % MOD;
				// cout << "j "<< j << " ways "<< ways << endl;
				if(a[j] < x) {ans += w * (x - a[j]); ans %= MOD;}
				if(b[j] < x) {ans += w * (x - b[j]); ans %= MOD;}
				dpLft[j] += ways; dpLft[j] %= MOD;
				ways = (ways * lft[j]) % MOD;
			}
			ways = 1;
			for(int j = N-1; j > i; j--){
				ways = (ways * lft[j]) % MOD;
			}
			for(int j = i-1; j >= 0; j--){
				long long w = (ways * dpLft[j]) % MOD;
				// cout << "j "<< j << " ways "<< ways << endl;
				if(a[j] < x) {ans += w * (x - a[j]); ans %= MOD;}
				if(b[j] < x) {ans += w * (x - b[j]); ans %= MOD;}
				// if(a[i] < x) {totalWater[i] += w * (x - a[i]); totalWater[i] %= MOD;}
				// if(b[i] < x) {totalWater[i] += w * (x - b[i]); totalWater[i] %= MOD;}
				dpRght[j] += ways; dpRght[j] %= MOD;
				ways = (ways * lft[j]) % MOD;
			}
			// for(int j = 0; j < N; j++){
			// 	cout << "j "<< j << " lft "<< lft[j] << " dpL "<< dpLft[j] << " dpR "<< dpRght[j] << endl;
			// }
			lft[i]--;
		}
		cout << ans << "\n";
	}else{
		//Case <= 2.
		long long ans = 0;
		for(int i = 0; i < N; i++){
			long long ways1 = (binpow(2, i) + MOD - 1) % MOD;
			long long ways2 = (binpow(2, N - i - 1) +  MOD - 1) % MOD;
			ans += (ways1 * ways2) % MOD;
		}
		cout << ans << "\n";
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30