#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define clean(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int long long
using pii = pair<int,int>;
using ll = long long;
const int maxn = 1e5+5;
const int maxc = 25;
const int inf = 2e9;
const int mod = 1000000007;
int n,c,q,a[maxn],b[maxn],dp[maxn][maxc];
int32_t main () {
//freopen("in","r",stdin); freopen("out","w",stdout);
ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
cin >> n >> c;
for(int i=1;i<=n;i++) cin >> a[i] , a[i] %= mod;
for(int i=1;i<=n;i++) cin >> b[i] , b[i] %= mod;
dp[0][0] = 1;
for(int i=1;i<=n;i++) {
dp[i][0] = dp[i-1][0]*b[i]%mod;
for(int j=1;j<=i;j++)
dp[i][j] = (a[i]*dp[i-1][j-1]%mod + b[i]*dp[i-1][j]%mod)%mod;
}
cin >> q;
while(q--) {
int idx,aa,bb;
cin >> idx >> aa >> bb;
a[idx] = aa%mod;
b[idx] = bb%mod;
for(int i=idx;i<=n;i++) {
dp[i][0] = (dp[i-1][0]*b[i])%mod;
for(int j=1;j<=i;j++)
dp[i][j] = (a[i]*dp[i-1][j-1]%mod + b[i]*dp[i-1][j]%mod)%mod;
}
int ans = 0;
for(int i=c;i<=n;i++)
ans = (ans + dp[n][i])%mod;
cout << ans << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2083 ms |
752 KB |
Output isn't correct |
| 2 |
Incorrect |
2045 ms |
620 KB |
Output isn't correct |
| 3 |
Incorrect |
1137 ms |
748 KB |
Output isn't correct |
| 4 |
Execution timed out |
4032 ms |
8696 KB |
Time limit exceeded |
| 5 |
Execution timed out |
4064 ms |
9580 KB |
Time limit exceeded |
| 6 |
Execution timed out |
4064 ms |
9492 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4024 ms |
9112 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4022 ms |
9280 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4074 ms |
9300 KB |
Time limit exceeded |
| 10 |
Execution timed out |
4073 ms |
9104 KB |
Time limit exceeded |
