제출 #1368568

#제출 시각아이디문제언어결과실행 시간메모리
1368568raduvFlooding Wall (BOI24_wall)C++20
48 / 100
4705 ms8236 KiB
#include <bits/stdc++.h>
const int MAXN = 500'000;
const int MOD = 1'000'000'007;
/*
voi folosi formula :
S(h) = n * 2 ^ n - sum{prod{k <= i, c_k} * 2 ^ (n - i)}
                 - sum{prod{k >= i, c_k} * 2 ^ (i - 1)}
                 + n * prod{c_i}

unde c_i = (a_i < h + b_i < h)

voi face brutul in O(n ^ 2) mai intai, pentru fiecare H voi calcula S(h)

*/
int n;
int a[MAXN + 1], b[MAXN + 1], c[MAXN + 1];
int pow2[MAXN + 1];
void read_data() {
  std::cin >> n;
  for( int i = 1; i <= n; i++ )
    std::cin >> a[i];
  for( int i = 1; i <= n; i++ )
    std::cin >> b[i];
}
void precompute_power() {
  pow2[0] = 1;
  for( int i = 1; i <= n; i++ )
    pow2[i] = 2 * pow2[i - 1] % MOD;
}
int compute_sum(int h) {
  int sum = 0;
  sum = 1LL * n * pow2[n] % MOD;
  for( int i = 1; i <= n; i++ )
    c[i] = (a[i] < h) + (b[i] < h);

  int prod = 1;
  for( int i = 1; i <= n; i++ ) {
    prod = 1LL * prod * c[i] % MOD;
    sum = (sum - (1LL * prod * pow2[n - i]) % MOD + MOD) % MOD;
  }
  prod = 1;
  for( int i = n; i >= 1; i-- ) {
    prod = 1LL * prod * c[i] % MOD;
    sum = (sum - (1LL * prod * pow2[i - 1]) % MOD + MOD) % MOD;
  }
  sum = (sum + 1LL * prod * n) % MOD;
  return sum;
}
int overall_sum() {
  int sum = 0;
  for( int i = 1; i <= n; i++ ) {
    sum = (sum + 1LL * (a[i] + b[i]) * pow2[n - 1]) % MOD;
  }
  return sum;
}
int height_total() {
  int sum = 0;
  for( int h = 1; h <= 1000; h++ ) {
    sum = (sum + compute_sum(h)) % MOD;
  }
  return sum;
}
int main() {
  read_data();
  precompute_power();
  int h_sum = height_total();
  int tot_sum = overall_sum();
  int ans = (h_sum - tot_sum + MOD) % MOD;
  std::cout << ans << "\n";
  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…