QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460137#5532. Kangaroofryan51 389ms138584kbC++202.3kb2024-07-01 03:11:452024-07-01 03:11:46

Judging History

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

  • [2024-07-01 03:11:46]
  • 评测
  • 测评结果:51
  • 用时:389ms
  • 内存:138584kb
  • [2024-07-01 03:11:45]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 205;
const int mod = 1e9+7;

int n, cs, cf;
int dp[2][mxn][mxn][mxn];
int ans = 0;

signed main() {
	
	scanf("%lld%lld%lld", &n, &cs, &cf);
	memset(dp, 0, sizeof(dp));
	if (cs > cf) swap(cs,cf);
	dp[0][cs-1][cf-cs-1][n-cf] = 1;
	dp[1][cs-1][cf-cs-1][n-cf] = 1;
	
	for (int rem = n; rem >= 0; rem--) {
		for (int a1 = 0; a1 < n; a1++) {
			for (int a2 = 0; a2 < n; a2++) {
				int dir, a3;
				//dir = 0 : away
				dir = 0;
				if (rem-a1-a2 >= 0)  {
					a3 = rem-a1-a2;
					if (a1) {
						for (int na1 = 0; na1 < a1; na1++) {
							int na2 = a1-na1-1+a2;
							dp[1][na1][na2][a3] += dp[dir][a1][a2][a3];
							dp[1][na1][na2][a3] %= mod;
						}
					}
				}
				//dir = 1 : towards
				dir = 1;
				if (rem-a1-a2 >= 0) {
					a3 = rem-a1-a2;
					//case 1 - before
					if (a2) {
						for (int na2 = 0; na2 < a2; na2++) {
							int na1 = a1+a2-na2-1;
							dp[0][na1][na2][a3] += dp[dir][a1][a2][a3];
							dp[0][na1][na2][a3] %= mod;
						}
						
//						dp[0][a1][a2-1][a3] += dp[dir][a1][a2][a3];
//						dp[0][a1][a2-1][a3] %= mod;
					}
					//case 2 - after
					for (int na2 = 0; na2 < a3; na2++) {
						int na1 = a3-na2-1;
						int na3 = a1+a2;
						dp[1][na1][na2][na3] += dp[dir][a1][a2][a3];
						dp[1][na1][na2][na3] %= mod;
					}
				}
				if (rem == 0 && rem-a1-a2 >= 0) {
					a3 = rem-a1-a2;
					ans += dp[1][a1][a2][a3];
				}
	/*			if (rem-a1-a2 >= 0) {
					int a3 = rem-a1-a2;
					if (dp[0][a1][a2][a3]) {
						printf("0 %d %d %d : %d\n", a1,a2,a3,dp[0][a1][a2][a3]);
					}
					if (dp[1][a1][a2][a3]) {
						printf("1 %d %d %d : %d\n", a1,a2,a3,dp[1][a1][a2][a3]);
					}
				}
	*/
			}
		}
	}
	
	printf("%lld", ans);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 11ms
memory: 138536kb

input:

7 3 6

output:

14

result:

ok 1 number(s): "14"

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 30
Accepted
time: 0ms
memory: 138400kb

input:

39 36 32

output:

964903316

result:

ok 1 number(s): "964903316"

Test #3:

score: 0
Accepted
time: 11ms
memory: 138456kb

input:

26 1 26

output:

955348527

result:

ok 1 number(s): "955348527"

Test #4:

score: 0
Accepted
time: 4ms
memory: 138516kb

input:

40 11 33

output:

695661890

result:

ok 1 number(s): "695661890"

Test #5:

score: 0
Accepted
time: 4ms
memory: 138524kb

input:

39 39 38

output:

717149364

result:

ok 1 number(s): "717149364"

Test #6:

score: 0
Accepted
time: 8ms
memory: 138448kb

input:

40 10 25

output:

912929610

result:

ok 1 number(s): "912929610"

Test #7:

score: 0
Accepted
time: 8ms
memory: 138536kb

input:

37 25 23

output:

250748685

result:

ok 1 number(s): "250748685"

Test #8:

score: 0
Accepted
time: 11ms
memory: 138540kb

input:

39 2 38

output:

624060592

result:

ok 1 number(s): "624060592"

Test #9:

score: 0
Accepted
time: 12ms
memory: 138476kb

input:

40 18 22

output:

739993796

result:

ok 1 number(s): "739993796"

Test #10:

score: 0
Accepted
time: 4ms
memory: 138484kb

input:

40 11 35


output:

135213497

result:

ok 1 number(s): "135213497"

Subtask #3:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 15
Accepted
time: 383ms
memory: 138444kb

input:

199 100 70

output:

914653136

result:

ok 1 number(s): "914653136"

Test #12:

score: 0
Accepted
time: 290ms
memory: 138544kb

input:

187 3 40

output:

928785584

result:

ok 1 number(s): "928785584"

Test #13:

score: 0
Accepted
time: 379ms
memory: 138448kb

input:

199 198 197

output:

38412688

result:

ok 1 number(s): "38412688"

Test #14:

score: 0
Accepted
time: 384ms
memory: 138444kb

input:

200 40 140

output:

367088143

result:

ok 1 number(s): "367088143"

Test #15:

score: 0
Accepted
time: 377ms
memory: 138476kb

input:

199 111 3

output:

870834793

result:

ok 1 number(s): "870834793"

Test #16:

score: 0
Accepted
time: 388ms
memory: 138584kb

input:

200 133 73

output:

343127012

result:

ok 1 number(s): "343127012"

Test #17:

score: 0
Accepted
time: 218ms
memory: 138400kb

input:

178 15 163

output:

160852284

result:

ok 1 number(s): "160852284"

Test #18:

score: 0
Accepted
time: 365ms
memory: 138536kb

input:

197 43 79

output:

332057544

result:

ok 1 number(s): "332057544"

Test #19:

score: 0
Accepted
time: 389ms
memory: 138516kb

input:

200 33 79

output:

742545318

result:

ok 1 number(s): "742545318"

Subtask #4:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #20:

score: 0
Runtime Error

input:

658 169 438

output:


result: