Submission #1041759

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041759	2024-08-02T07:49:34 Z	vjudge1	Ljetopica (COI19_ljetopica)	C++17	100 / 100	12 ms	24160 KB

ljetopica

#include <bits/stdc++.h>
using namespace std;

#define int long long

int const N=1005;
int const mod=1e9+7;

int choose[N][N];
int dp[N][N][2];
int pow2[N];
int n,k;
string low,high,com;

void fill_choose(){
	for (int i = 0; i < N; ++i)
		for(int j=0;j<=i;j++){
			if(j==0)
				choose[i][j]=1;
			else
				choose[i][j]=(choose[i-1][j]+choose[i-1][j-1])%mod;
		}}
void fill_dp(){
	int len=n-1;
	dp[0][0][0]=dp[0][0][1]=pow2[len];
	for (int i = 1; i <=len; ++i)
		for (int j = 0; j <=k; ++j){
			//p==0
			if(com[len-i]=='L'){
				dp[i][j][0]=dp[i-1][j][0];
				if(j>0)
					dp[i][j][0]+=(dp[i-1][j-1][1]+((choose[i-1][j-1]*pow2[i-1])%mod))%mod;
				dp[i][j][0]%=mod;
			}
			else{
				dp[i][j][0]=(dp[i-1][j][0]+((choose[i-1][j]*pow2[i-1])%mod))%mod;
				if(j>0)
					dp[i][j][0]+=dp[i-1][j-1][1];
				dp[i][j][0]%=mod;
			}
			//p==1
			if(com[len-i]=='R'){
				dp[i][j][1]=dp[i-1][j][1];
				if(j>0)
					dp[i][j][1]+=(dp[i-1][j-1][0]+((choose[i-1][j-1]*pow2[i-1])%mod))%mod;
				dp[i][j][1]%=mod;
			}
			else{
				dp[i][j][1]=(dp[i-1][j][1]+((choose[i-1][j]*pow2[i-1])%mod))%mod;
				if(j>0)
					dp[i][j][1]+=dp[i-1][j-1][0];
				dp[i][j][1]%=mod;
			}
		}}
void fill_pow(){
	pow2[0]=1;
	for (int i = 1; i < N; ++i)
		pow2[i]=(pow2[i-1]*2)%mod;}
int less_than(string s,int pr){
	int len=n-1,prev=0,ans=0,used=0;
	for(int i=1;i<=len;i++){
		bool c=(pr==0 && com[i-1]=='R')||(pr==1 && com[i-1]=='L');
		if(s[i]=='0'){
			if(c){
				used++;
				pr^=1;
			}
			continue;
		}
		if(used+c<=k){
			ans+=(prev*((choose[len-i][k-(used+c)])%mod))%mod;
			ans+=dp[len-i][k-(used+c)][pr^c];
			ans%=mod;

		}
		if(c==0){
			pr^=1;
			used++;
		}
		prev+=pow2[len-i];
		prev%=mod;
	}
	return ans;
}
signed main(){
	fill_choose();
	//input
	cin>>n>>k;
	cin>>com>>low>>high;
	if(low>high){
		cout<<0<<endl;
		return 0;
	}
	//solve
	fill_pow();fill_dp();
	// int ans=(pow2[n]*(choose[n-1][k]))%mod;
	int ans=((less_than(high,0)-less_than(low,0))+mod)%mod;
	ans+=((less_than(high,1)-less_than(low,1))+mod)%mod;
	ans%=mod;
	for(int i=1;i<=n;i++)
		if(high[i-1]=='1')
			ans=(ans+pow2[n-i])%mod;
	// }
	cout<<ans%mod<<endl;
	return 0;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	23900 KB	Output is correct
2	Correct	4 ms	24040 KB	Output is correct
3	Correct	3 ms	23896 KB	Output is correct
4	Correct	4 ms	23900 KB	Output is correct
5	Correct	5 ms	23900 KB	Output is correct
6	Correct	3 ms	21848 KB	Output is correct
7	Correct	4 ms	21932 KB	Output is correct
8	Correct	3 ms	19804 KB	Output is correct

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	11612 KB	Output is correct
2	Correct	2 ms	11612 KB	Output is correct
3	Correct	2 ms	11612 KB	Output is correct
4	Correct	2 ms	11612 KB	Output is correct
5	Correct	2 ms	11612 KB	Output is correct
6	Correct	2 ms	11716 KB	Output is correct
7	Correct	3 ms	11608 KB	Output is correct
8	Correct	2 ms	11612 KB	Output is correct
9	Correct	3 ms	11612 KB	Output is correct
10	Correct	3 ms	11612 KB	Output is correct
11	Correct	3 ms	11612 KB	Output is correct
12	Correct	2 ms	11612 KB	Output is correct
13	Correct	3 ms	11612 KB	Output is correct
14	Correct	2 ms	11612 KB	Output is correct
15	Correct	2 ms	11612 KB	Output is correct

Subtask #3
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	23900 KB	Output is correct
2	Correct	8 ms	23896 KB	Output is correct
3	Correct	8 ms	23900 KB	Output is correct
4	Correct	12 ms	24144 KB	Output is correct
5	Correct	5 ms	23900 KB	Output is correct
6	Correct	11 ms	24156 KB	Output is correct
7	Correct	5 ms	23900 KB	Output is correct
8	Correct	6 ms	24092 KB	Output is correct
9	Correct	3 ms	23896 KB	Output is correct
10	Correct	8 ms	24092 KB	Output is correct

Subtask #4
61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	23900 KB	Output is correct
2	Correct	4 ms	24040 KB	Output is correct
3	Correct	3 ms	23896 KB	Output is correct
4	Correct	4 ms	23900 KB	Output is correct
5	Correct	5 ms	23900 KB	Output is correct
6	Correct	3 ms	21848 KB	Output is correct
7	Correct	4 ms	21932 KB	Output is correct
8	Correct	3 ms	19804 KB	Output is correct
9	Correct	3 ms	11612 KB	Output is correct
10	Correct	2 ms	11612 KB	Output is correct
11	Correct	2 ms	11612 KB	Output is correct
12	Correct	2 ms	11612 KB	Output is correct
13	Correct	2 ms	11612 KB	Output is correct
14	Correct	2 ms	11716 KB	Output is correct
15	Correct	3 ms	11608 KB	Output is correct
16	Correct	2 ms	11612 KB	Output is correct
17	Correct	3 ms	11612 KB	Output is correct
18	Correct	3 ms	11612 KB	Output is correct
19	Correct	3 ms	11612 KB	Output is correct
20	Correct	2 ms	11612 KB	Output is correct
21	Correct	3 ms	11612 KB	Output is correct
22	Correct	2 ms	11612 KB	Output is correct
23	Correct	2 ms	11612 KB	Output is correct
24	Correct	8 ms	23900 KB	Output is correct
25	Correct	8 ms	23896 KB	Output is correct
26	Correct	8 ms	23900 KB	Output is correct
27	Correct	12 ms	24144 KB	Output is correct
28	Correct	5 ms	23900 KB	Output is correct
29	Correct	11 ms	24156 KB	Output is correct
30	Correct	5 ms	23900 KB	Output is correct
31	Correct	6 ms	24092 KB	Output is correct
32	Correct	3 ms	23896 KB	Output is correct
33	Correct	8 ms	24092 KB	Output is correct
34	Correct	12 ms	24152 KB	Output is correct
35	Correct	5 ms	24092 KB	Output is correct
36	Correct	7 ms	24100 KB	Output is correct
37	Correct	10 ms	24156 KB	Output is correct
38	Correct	5 ms	24156 KB	Output is correct
39	Correct	11 ms	24156 KB	Output is correct
40	Correct	4 ms	23900 KB	Output is correct
41	Correct	9 ms	23900 KB	Output is correct
42	Correct	9 ms	23900 KB	Output is correct
43	Correct	9 ms	23896 KB	Output is correct
44	Correct	10 ms	24156 KB	Output is correct
45	Correct	4 ms	23912 KB	Output is correct
46	Correct	9 ms	23900 KB	Output is correct
47	Correct	8 ms	23996 KB	Output is correct
48	Correct	7 ms	23900 KB	Output is correct
49	Correct	3 ms	23900 KB	Output is correct
50	Correct	10 ms	24156 KB	Output is correct
51	Correct	8 ms	24156 KB	Output is correct
52	Correct	9 ms	24108 KB	Output is correct
53	Correct	10 ms	24156 KB	Output is correct
54	Correct	4 ms	23900 KB	Output is correct
55	Correct	10 ms	24160 KB	Output is correct
56	Correct	10 ms	24156 KB	Output is correct
57	Correct	5 ms	23900 KB	Output is correct
58	Correct	10 ms	23900 KB	Output is correct

Submission #1041759

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 17.0 / 17.0

Subtask #4 61.0 / 61.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
17.0 / 17.0

Subtask #4
61.0 / 61.0