제출 #1140135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140135		AbdullahIshfaq	Flooding Wall (BOI24_wall)	C++20	58 / 100	5092 ms	29828 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
void solve(){
	int n;
	cin >> n;
	pair<ll,ll> arr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i].first;
	}
	for(int i = 0; i < n; i++){
		cin >> arr[i].second;
	}
	vector<pair<ll,ll>> rngs;
	for(int i = 0; i < n; i++){
		if(arr[i].first > arr[i].second){
			swap(arr[i].first, arr[i].second);
		}
		rngs.push_back({arr[i].first, i});
		rngs.push_back({arr[i].second, i});
	}
	sort(rngs.rbegin(), rngs.rend());
	ll ans = 0;
	int st[n], add1[n] = {}, add2[n] = {};
	for(int i = 0; i < n; i++){
		st[i] = 2;
	}
	for(auto [h, i] : rngs){
		ll res = 1;
		for(int j = 0; j < i; j++){
			res = res * st[j] % MOD;
		}
		for(int j = i + 1; j < n; j++){
			if(h > arr[j].first){
				ans += res * add1[j] % MOD *(h - arr[j].first) % MOD;
			}
			if(h > arr[j].second){
				ans += res * add1[j] % MOD *(h - arr[j].second) % MOD;
			}
			add2[j] += res;
			add2[j] %= MOD;
			res = (res * st[j]) % MOD;
		}
		res = 1;
		for(int j = i + 1; j < n; j++){
			res = res * st[j] % MOD;
		}
		for(int j = i - 1; j >= 0; j--){
			if(h > arr[j].first){
				ans += res * add2[j] % MOD * (h - arr[j].first)%MOD;
			}
			if(h > arr[j].second){
				ans += res * add2[j] % MOD * (h - arr[j].second)%MOD;
			}
			add1[j] += res;
			add1[j] %= MOD;
			res = (res * st[j])%MOD;
		}
		st[i]--;
	}
	cout << ans % MOD << '\n';
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i++){
		solve();
	}
}

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