QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#863772	#8116. Kocke	Unforgettablepl	50	14ms	26112kb	C++20	910b	2025-01-19 22:08:24	2025-01-19 22:08:25

Judging History

你现在查看的是最新测评结果

[2025-01-19 22:08:25]
评测

测评结果：50
用时：14ms
内存：26112kb

查看

[2025-01-19 22:08:24]
提交

answer

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

#define int long long


const int modulo = 1e9+7;

int32_t main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n,K;
	cin >> n >> K;
	vector DP(n+1,vector(K+1,vector(K+1,vector(2,0ll))));
	for(int i=1;i<=K;i++)DP[1][i][i][0]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=K;j++){
			for(int k=j+1;k<=K;k++){
				DP[i][j][k][0]=DP[i-2][j][k][0]+DP[i-1][j+1][k][0];
				if(i-(k-j)>=1)DP[i][j][k][0]+=DP[i-(k-j)][j+1][k][1];
				DP[i][j][k][0]%=modulo;

				DP[i][j][k][1]=DP[i-2][j][k][1]+DP[i-1][j][k-1][1];
				if(i-(k-j)>=1)DP[i][j][k][1]+=DP[i-(k-j)][j][k-1][0];
				DP[i][j][k][1]%=modulo;
			}
		}
	}
	int ans = 0;
	for(int l=1;l<=K;l++){
		for(int r=l;r<=K;r++){
			ans = (ans+DP[n][l][r][0]+DP[n][l][r][1])%modulo;
			if(l!=r)ans = (ans+DP[n-1][l][r][0]+DP[n-1][l][r][1])%modulo;
		}
	}
	cout << ans << '\n';
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 0ms

memory: 3584kb

input:

2 3

output:

result:

ok single line: '4'

Test #2:

score: 20

Accepted

time: 0ms

memory: 3840kb

input:

5 18

output:

result:

ok single line: '218'

Test #3:

score: 20

Accepted

time: 0ms

memory: 3968kb

input:

9 18

output:

result:

ok single line: '1980'

Test #4:

score: 20

Accepted

time: 0ms

memory: 3840kb

input:

15 9

output:

result:

ok single line: '9564'

Test #5:

score: 20

Accepted

time: 0ms

memory: 3968kb

input:

16 18

output:

result:

ok single line: '66116'

Test #6:

score: 20

Accepted

time: 0ms

memory: 3712kb

input:

18 10

output:

result:

ok single line: '43140'

Test #7:

score: 20

Accepted

time: 1ms

memory: 3968kb

input:

18 18

output:

result:

ok single line: '170888'

Subtask #2:

score: 30

Accepted

Dependency #1:

100%

Accepted

Test #8:

score: 30

Accepted

time: 0ms

memory: 4224kb

input:

2 49

output:

result:

ok single line: '96'

Test #9:

score: 30

Accepted

time: 0ms

memory: 4352kb

input:

7 38

output:

result:

ok single line: '1598'

Test #10:

score: 30

Accepted

time: 1ms

memory: 3840kb

input:

19 6

output:

result:

ok single line: '5524'

Test #11:

score: 30

Accepted

time: 4ms

memory: 8192kb

input:

31 49

output:

369127208

result:

ok single line: '369127208'

Test #12:

score: 30

Accepted

time: 1ms

memory: 6272kb

input:

44 30

output:

310756420

result:

ok single line: '310756420'

Test #13:

score: 30

Accepted

time: 0ms

memory: 3712kb

input:

49 2

output:

result:

ok single line: '2'

Test #14:

score: 30

Accepted

time: 3ms

memory: 11264kb

input:

50 50

output:

375733561

result:

ok single line: '375733561'

Subtask #3:

score: 0

Memory Limit Exceeded

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #15:

score: 30

Accepted

time: 14ms

memory: 26112kb

input:

2 319

output:

result:

ok single line: '636'

Test #16:

score: 30

Accepted

time: 3ms

memory: 13824kb

input:

89 44

output:

999831996

result:

ok single line: '999831996'

Test #17:

score: 0

Memory Limit Exceeded

input:

280 279

output:

332244975

result:

Subtask #4:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted