Submission #1015027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015027		doducanh	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	61 ms	6224 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define h first
#define w second
pair<int,int>a[100005];
int f[100005];
int dp[100005];
const int mod=1e9+7;
int n;
int mul(int a,int b)
{
    return a*b%mod;
}
int sum(int a)
{
    return (a*(a+1)/2)%mod;
}
main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].h;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
        f[i]=(f[i-1]+a[i].w)%mod;
    }
    int ans=0;
    stack<int>s;
    s.push(0);
    for(int i=1;i<=n;i++){
        while(s.size()&&a[s.top()].h>=a[i].h)s.pop();
        int len=(f[i]-f[s.top()]+mod)%mod;
        int l1=(len-a[i].w+mod)%mod;
        int A=0,B=0;
        (A+=mul(sum(a[i].h),sum(a[i].w)))%=mod;
        (A+=(mul(mul(l1,sum(a[i].h)),a[i].w)))%=mod;
        (B+=mul(dp[s.top()],a[i].w))%=mod;
        dp[i]=(dp[s.top()]+mul(len,sum(a[i].h)))%mod;
        ans=(ans+A+B)%mod;
        s.push(i);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

fancyfence.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main()
      | ^~~~

• 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