Submission #1168494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168494		LmaoLmao	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	21 ms	4380 KiB

fancyfence

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;

const int N = 2e5+5;
const int INF = 1e9;

int MOD=1e9+7;
int dp[100005][2];
int a[100005],w[100005];
 
int cal(int x,int y) {
  //if(( ((x-y+1)*(x+y)%MOD)*((MOD+1)/2) )%MOD<0) cout << x << ' ' << y << endl;
  return ( ((x-y+1)*(x+y)%MOD)*((MOD+1)/2) )%MOD;
}
 

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) {
      cin >> a[i];
    }
    for(int i=1;i<=n;i++) {
      cin >> w[i];
      w[i]+=w[i-1];
    }
    stack<int> st;
    int ans=0;
    for(int i=1;i<=n;i++) {
      while(!st.empty() && a[st.top()]>a[i]) {
        st.pop();
      }
      int pos;
      if(st.empty()) pos=0; else pos=st.top();
      int res=(cal((w[i]-w[pos])%MOD,(w[i-1]-w[pos]+1)%MOD)*cal(a[i],1))%MOD;
      dp[i][1]=((w[i]-w[pos])%MOD*cal(a[i],1)%MOD+dp[pos][1])%MOD;
      dp[i][0]=(res + dp[pos][1]*((w[i]-w[i-1])%MOD)%MOD )%MOD;
      ans=(ans+dp[i][0])%MOD;
      //cout << dp[pos][1] << endl;
      st.push(i);
    }
    cout << (ans+MOD)%MOD;
    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