제출 #1290903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290903		loom	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	20 ms	5976 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int mod = 1e9+7;

void solve(){
   int n;
   cin>>n;

   int h[n], w[n], pre[n];
   for(int i = 0; i < n; i++) cin>>h[i];
   for(int i = 0; i < n; i++) cin>>w[i], pre[i] = ((i == 0 ? 0 : pre[i-1]) + w[i]) % mod;

   vector<pair<int,int>> v;
   int ps[n];

   for(int i = 0; i < n; i++){
      while(!v.empty() and v.back().second >= h[i]) v.pop_back();

      if(v.empty()) ps[i] = -1;
      else ps[i] = v.back().first;

      v.push_back({i, h[i]});
   }

   int ans = 0;
   int dp[n];

   for(int i = 0; i < n; i++){
      int j = ps[i];
      int sum = (pre[i] - (j == -1 ? 0 : pre[j]) + mod) % mod;

      dp[i] = sum * (h[i] * (h[i] + 1) / 2 % mod) % mod + (j == -1 ? 0 : dp[j]);
      dp[i] %= mod;
   
      ans += dp[i] * w[i];
      ans %= mod;

      ans += mod - w[i] * w[i] % mod * (h[i] * (h[i] + 1) / 2 % mod) % mod;
      ans += w[i] * (w[i] + 1) / 2 % mod * (h[i] * (h[i] + 1) / 2 % mod);
      ans %= mod;
   }

   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();
}

• 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