Submission #1008253

#TimeUsernameProblemLanguageResultExecution timeMemory
1008253KryzFancy Fence (CEOI20_fancyfence)C++17
0 / 100
1 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<ll,ll> #define REP(i,x,y) for(ll i=x;i<=y;i++) #define freeopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #define mod 1000000007 #define pb push_back #define mk make_pair #define ll long long #define foor(x,vec) for(auto x:vec ){cout<<x<<" ";} #define fi first #define se second #define MAXN 700069 #define lld long double #define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ffl fflush(stdout) #define sst string #define pii pair<ll,ll> ll mvx[]={0,0,-1,1}; ll mvy[]={1,-1,0,0}; ll n,q; ll a,b; ll h[MAXN],w[MAXN]; ll ps[MAXN]; ll dp[MAXN]; ll idx[MAXN]; ll add(ll x, ll y) { ll res=(x+y)%mod; return res; } ll cal(ll x) { return (ll)((1ll * x * (x + 1) / 2) % mod); } ll mult(ll x, ll y) { return (int)((1ll * x * y) % mod); } int main(){ cin>>n; REP(i,1,n)cin>>h[i]; REP(i,1,n)cin>>w[i]; REP(i,1,n){ ps[i]=ps[i-1]+w[i]; ps[i]%=mod; } vector <ll> vec; vec.pb(0); for(ll i = 1; i <= n; i++) { while(vec.size() && h[i] < h[vec.back()]) { vec.pop_back(); } assert(vec.size()); idx[i] = vec.back(); vec.pb(i); } ll ans=0; REP(i,1,n){ ll val = mult(dp[idx[i]], w[i]); // ini buat sebelumnya val = add(val, mult( (ps[i - 1]-ps[idx[i]]), mult(w[i], cal(h[i]) ) ) ); // ini buat diantara val = add(val, mult(cal(w[i] + 1), cal(h[i] ))); // ini buat sendiri ans = add(ans, val); dp[i] = add(dp[idx[i]], mult((ps[i]-ps[idx[i]])%mod, cal(h[i] ) )); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...