Submission #1004911

#TimeUsernameProblemLanguageResultExecution timeMemory
1004911pavementFlooding Wall (BOI24_wall)C++17
17 / 100
5070 ms600 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back const int MOD = (int)1e9 + 7, INV_2 = (MOD + 1) / 2; int N, glob, a[500005], b[500005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 1; i <= N; i++) { cin >> a[i]; } for (int i = 1; i <= N; i++) { cin >> b[i]; if (a[i] > b[i]) { swap(a[i], b[i]); } } for (int i = 1; i <= N; i++) { for (int h : {a[i], b[i]}) { int expected = 0; vector<int> probs = {1}; for (int v = h + 1; v <= 1001; v++) { int lft_prob = 1, rig_prob = 1; for (int j = 1; j < i; j++) { int cur_prob = INV_2; if (a[j] >= v) { cur_prob = 0; } else if (b[j] < v) { cur_prob = 1; } lft_prob = ((ll)lft_prob * cur_prob) % MOD; } lft_prob = (1 - lft_prob + MOD) % MOD; for (int j = i + 1; j <= N; j++) { int cur_prob = INV_2; if (a[j] >= v) { cur_prob = 0; } else if (b[j] < v) { cur_prob = 1; } rig_prob = ((ll)rig_prob * cur_prob) % MOD; } rig_prob = (1 - rig_prob + MOD) % MOD; int p = (ll)lft_prob * rig_prob % MOD; probs.pb(p); } for (int v = 0; v + 1 < (int)probs.size(); v++) { int tmp = (probs[v] - probs[v + 1] + MOD) % MOD; expected = (expected + (ll)(v + h) * tmp % MOD) % MOD; } expected = (expected - h + MOD) % MOD; glob = (glob + expected) % MOD; } } for (int rep = 0; rep < N - 1; rep++) { glob = (glob * 2) % MOD; } cout << glob << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...