Submission #430965

#	Time	Username	Problem	Language	Result	Execution time	Memory
430965		Pety	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	52 ms	4196 KiB

fancyfence

#include <bits/stdc++.h>
     
using namespace std;

#define ll long long

const int mod = 1e9+7;

int n;
stack<int>st;
int h[100002], w[100002], dp[100002];
int sum[100002];

int logpow(int a, int b) {
  int ans = 1, d = a;
  while (b) {
    if (b & 1)
      ans = 1LL * ans * d % mod;
    b >>= 1;
    d = 1LL * d * d % mod;
  }
  return ans;
}

int calc (int w, int h) {
  ll a1 = 1ll * w * (w + 1) / 2 % mod;
  ll a2 = 1ll * h * (h + 1) / 2 % mod;
  return 1ll * a1 * a2 % mod;
}


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> h[i];
  for (int i = 1; i <= n; i++)
    cin >> w[i];
  st.push(0);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    while (h[st.top()] >= h[i]) {
      st.pop();
    }
    sum[i] = sum[i - 1] + w[i];
    if (sum[i] >= mod)
      sum[i] -= mod;
    int x = st.top();
    st.push(i);
    if (x) {
      int val = dp[x] - calc(w[x], h[x]);
      if (val < 0)
        val += mod;
      val = 1ll * val * logpow(w[x], mod - 2) % mod;
      dp[i] = 1ll * val * w[i] % mod; 
      int a1 = 1ll * h[x] * (h[x] + 1) / 2 % mod;
      dp[i] = dp[i] + 1ll * w[x] * w[i] % mod * a1 % mod;
      if (dp[i] >= mod)
        dp[i] -= mod;
    }
    int a1 = 1ll * h[i] * (h[i] + 1) / 2 % mod;
    dp[i] = dp[i] + 1ll * w[i] * (sum[i - 1] - sum[x] + mod) % mod * a1 % mod;
    if (dp[i] >= mod)
      dp[i] -= mod;
    dp[i] = dp[i] + calc(w[i], h[i]);
    if (dp[i] >= mod)
      dp[i] -= mod;
    ans = (ans + dp[i]);
    if (ans >= mod)
      ans -= mod;
  }
  cout << ans;
  return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27