Submission #881497

#TimeUsernameProblemLanguageResultExecution timeMemory
881497Iliya_Fancy Fence (CEOI20_fancyfence)C++17
0 / 100
1 ms2648 KiB
//IN THE NAME OF GOD #include<bits/stdc++.h> #pragma GCC optimize("O2,unroll-loops") #define endl '\n' #define F first #define S second #define pii pair<int,int> #define all(x) x.begin(),x.end() #define pb push_back #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; typedef long double dll; #define int long long const int N = 1e5+7, mod = 1e9+7; int dp[N], h[N], w[N], sum[N]; vector<pii> vec; int power(int a, int b){ int ans = 1; while(b){ if (b&1) ans = ans * a % mod; a = a * a % mod; b/=2; } return ans; } int32_t main(){ fastio; vec.pb({1e9+1,0}); dp[0] = 0; int inv2 = power(2,mod-2); int n; cin >> n; for(int i=1; i<=n; i++) cin >> h[i]; for(int i=1; i<=n; i++){ cin >> w[i]; sum[i] = (sum[i-1] + w[i]) % mod; } for(int i=1; i<=n; i++){ while(vec.size() && vec.back().F >= h[i]) vec.pop_back(); int majw = (vec.size() ? sum[i] - sum[vec.back().S] : sum[i]); dp[i] = w[i] * (vec.size() ? dp[vec.back().S] : 0); vec.pb({h[i],i}); int ravh = (h[i] + 1) * h[i] * inv2 % mod; ravh %= mod; int en = majw, st = majw - h[i] + 1; int ravw = (st+en) * (en-st+1) * inv2 % mod; ravw %= mod; dp[i] = (dp[i] + ravw * ravh % mod) % mod; } int ans = 0; for(int i=1; i<=n; i++) ans = (ans + dp[i]) % mod; cout << ans << endl; return 0; }
#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...