oj.uz

Submission #79727

# Submission time Handle Problem Language Result Execution time Memory
79727 2018-10-15T16:50:51 Z KLPP Relativnost (COCI15_relativnost) C++14
42 / 140
 4000 ms 15524 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long int lld;
#define MOD 10007
int n,c;
void compute(lld a[],lld b[]){
	lld DP[n+1][c+1];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=c;j++)DP[i][j]=0;
	}DP[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=c;j++){
			DP[i+1][j]+=DP[i][j]*b[i];
			DP[i+1][j]%=MOD;
			DP[i+1][min(j+1,c)]+=DP[i][j]*a[i];
			DP[i+1][min(j+1,c)]%=MOD;
		}
	}
	/*for(int i=0;i<=n;i++){
		for(int j=0;j<=c;j++)cout<<DP[i][j]<<" ";
		cout<<endl;
	}*/
	cout<<DP[n][c]<<endl;
}
int main(){
	cin>>n>>c;
	lld a[n];
	lld b[n];
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	int q;
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		x--;
		lld y,z;
		cin>>y>>z;
		a[x]=y;
		b[x]=z;
		compute(a,b);
	}
	return 0;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 376 KB Output is correct
2 Correct 120 ms 628 KB Output is correct
3 Correct 113 ms 692 KB Output is correct
4 Execution timed out 4025 ms 4616 KB Time limit exceeded
5 Execution timed out 4037 ms 11156 KB Time limit exceeded
6 Execution timed out 4022 ms 15524 KB Time limit exceeded
7 Execution timed out 4038 ms 15524 KB Time limit exceeded
8 Execution timed out 4027 ms 15524 KB Time limit exceeded
9 Execution timed out 4033 ms 15524 KB Time limit exceeded
10 Execution timed out 4024 ms 15524 KB Time limit exceeded