제출 #1028548

#제출 시각아이디문제언어결과실행 시간메모리
1028548GrandTiger1729Flooding Wall (BOI24_wall)C++17
48 / 100
1515 ms10244 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10, C = 1010, MOD = 1e9 + 7; long long pw2[N]; void precalc() { pw2[0] = 1; for (int i = 1; i < N; i++) { pw2[i] = pw2[i - 1] * 2 % MOD; } } int main() { precalc(); cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n), b(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; if (a[i] > b[i]) { swap(a[i], b[i]); } } long long ans = 0; for (int i = 0; i < n; i++) { (ans += pw2[n - 1] * (b[i] - a[i] + (C - b[i]) * 2ll)) %= MOD; } vector<long long> coef(C, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < a[i]; j++) { coef[j] = 0; } for (int j = b[i]; j < C; j++) { (coef[j] *= 2) %= MOD; } long long tot = accumulate(coef.begin(), coef.end(), 0ll) % MOD; (ans += MOD - pw2[n - i - 1] * tot % MOD) %= MOD; } fill(coef.begin(), coef.end(), 1ll); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < a[i]; j++) { coef[j] = 0; } for (int j = b[i]; j < C; j++) { (coef[j] *= 2) %= MOD; } long long tot = accumulate(coef.begin(), coef.end(), 0ll) % MOD; (ans += MOD - pw2[i] * tot % MOD) %= MOD; } long long tot = accumulate(coef.begin(), coef.end(), 0ll) % MOD; (ans += n * tot % MOD) %= MOD; cout << ans << '\n'; return 0; }
#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...