oj.uz

답안 #374108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374108 2021-03-06T16:57:38 Z Nimbostratus Relativnost (COCI15_relativnost) C++17
0 / 140
 4000 ms 10012 KB 
#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 = 10007;
 
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=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;
		}
		int ans = 0;
		for(int i=c;i<=n;i++)
			ans = (ans + dp[n][i])%mod;
		cout << ans << endl;	
	}
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2904 ms 624 KB Output isn't correct
2 Incorrect 2778 ms 596 KB Output isn't correct
3 Incorrect 1589 ms 620 KB Output isn't correct
4 Execution timed out 4053 ms 9224 KB Time limit exceeded
5 Execution timed out 4085 ms 9776 KB Time limit exceeded
6 Execution timed out 4043 ms 9892 KB Time limit exceeded
7 Execution timed out 4097 ms 9396 KB Time limit exceeded
8 Execution timed out 4070 ms 10012 KB Time limit exceeded
9 Execution timed out 4061 ms 9568 KB Time limit exceeded
10 Execution timed out 4033 ms 9416 KB Time limit exceeded