Submission #987842

#TimeUsernameProblemLanguageResultExecution timeMemory
987842VMaksimoski008Fancy Fence (CEOI20_fancyfence)C++17
60 / 100
296 ms6484 KiB
#include <bits/stdc++.h> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() //#define int long long using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const double eps = 1e-9; ll exp(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = (ans * a) % mod; a = (a * a) % mod; b /= 2; } return ans; } ll inv(ll a) { return exp(a, mod - 2); } ll C(ll a) { return a * (a + 1) % mod * inv(2) % mod; } ll S(ll l, ll r) { return (C(r) - C(l-1) + mod) % mod; } int32_t main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n; cin >> n; vector<ll> h(n+1), w(n+1); for(int i=1; i<=n; i++) cin >> h[i]; for(int i=1; i<=n; i++) cin >> w[i]; set<ll> s; for(int i=1; i<=n; i++) s.insert(h[i]); if(s.size() == 1) { ll W = 0, H = h[1]; for(int i=1; i<=n; i++) W = (W + w[i]) % mod; cout << C(W) * C(H) % mod << '\n'; return 0; } bool inc = true; for(int i=1; i<n; i++) if(h[i] > h[i+1]) inc = false; if(inc) { ll ans = 0, W = 0; for(int i=n; i>=1; i--) { W = (W + w[i]) % mod; ans = (ans + S(W-w[i]+1, W) * C(h[i])) % mod; } cout << ans << '\n'; return 0; } if(n <= 1000) { ll ans = 0; vector<ll> pref(n+1); for(int i=1; i<=n; i++) pref[i] = (pref[i-1] + w[i]) % mod; auto query = [&](int l, int r) { return ( l > r ? 0 : (pref[r] - pref[l-1] + mod) % mod ); }; for(int i=1; i<=n; i++) { ll H = h[i]; for(int j=i+1; j<=n; j++) { H = min(H, h[j]); //cout << H << " " << query(i, j) << " " << query(i, j-1) << " " << query(i+1, j) << " " << query(i+1, j-1) << '\n'; ans = (ans + C(H) * C(query(i, j)) % mod) % mod; ans = (ans - C(H) * C(query(i, j-1)) + mod % mod) % mod; ans = (ans - C(H) * C(query(i+1, j)) + mod % mod) % mod; ans = (ans + C(H) * C(query(i+1, j-1)) + mod % mod) % mod; } } for(int i=1; i<=n; i++) ans = (ans + C(w[i]) * C(h[i])) % mod; cout << ans << '\n'; return 0; } 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...