QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#460194#5532. Kangaroofryan36 6ms4592kbC++202.1kb2024-07-01 05:56:442024-07-01 05:56:44

Judging History

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

  • [2024-07-01 05:56:44]
  • 评测
  • 测评结果:36
  • 用时:6ms
  • 内存:4592kb
  • [2024-07-01 05:56:44]
  • 提交

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 mod = 1e9+7;
const int mxn = 2e3;

int n, cs, cf;

#define v vector
#define s set
v<v<v<int>>> dpc, dpp;
s<array<int,3>> q[mxn];

signed main() {
	
	scanf("%lld%lld%lld", &n, &cs, &cf);
	dpc = v<v<v<int>>>(2,v<v<int>>(n,v<int>(n,0)));
	dpp = v<v<v<int>>>(2,v<v<int>>(n,v<int>(n,0)));
	if (cs > cf) swap(cs,cf);
	dpp[0][cs-1][cf-cs-1] = 1;
	dpp[1][cs-1][cf-cs-1] = 1;
	
	q[n-2].insert({0,cs-1,cf-cs-1});
	q[n-2].insert({1,cs-1,cf-cs-1});
	
	int ans = 0;
	
	for (int rem = n-2; rem >= 0; rem--) {
		for (auto query : q[rem]) {
			int dir = query[0];
			int a1 = query[1];
			int a2 = query[2];
			int a3 = rem-a1-a2;
//			printf("%lld %lld %lld %lld : %lld\n",dir,a1,a2,a3,dpp[dir][a1][a2]);
			if (rem == 0 && dir) {
				ans += dpp[dir][a1][a2];
				ans %= mod;
				continue;
			}
			
			if (dir == 0) {
				for (int na1 = 0; na1 < a1; na1++) {
					int na2 = a1-na1-1+a2;
					dpc[1][na1][na2] += dpp[dir][a1][a2];
					dpc[1][na1][na2] %= mod;
					q[rem-1].insert({1,na1,na2});
				}
			} else {
				for (int na2 = 0; na2 < a2; na2++) {
					int na1 = a1+a2-na2-1;
					dpc[0][na1][na2] += dpp[dir][a1][a2];
					dpc[0][na1][na2] %= mod;
					q[rem-1].insert({0,na1,na2});
				}
				for (int na2 = 0; na2 < a3; na2++) {
					int na1 = a3-na2-1;
					int na3 = a1+a2;
					dpc[1][na1][na2] += dpp[dir][a1][a2];
					dpc[1][na1][na2] %= mod;
					q[rem-1].insert({1,na1,na2});
				}
			}
			dpp[dir][a1][a2] = 0;
		}
		swap(dpp,dpc);
	}
	printf("%lld", ans);
	
	
	return 0;
}

详细

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 0ms
memory: 3916kb

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: 2ms
memory: 4336kb

input:

39 36 32

output:

964903316

result:

ok 1 number(s): "964903316"

Test #3:

score: 0
Accepted
time: 0ms
memory: 4224kb

input:

26 1 26

output:

955348527

result:

ok 1 number(s): "955348527"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4532kb

input:

40 11 33

output:

695661890

result:

ok 1 number(s): "695661890"

Test #5:

score: 0
Accepted
time: 1ms
memory: 4312kb

input:

39 39 38

output:

717149364

result:

ok 1 number(s): "717149364"

Test #6:

score: 0
Accepted
time: 6ms
memory: 4592kb

input:

40 10 25

output:

912929610

result:

ok 1 number(s): "912929610"

Test #7:

score: 0
Accepted
time: 5ms
memory: 4436kb

input:

37 25 23

output:

250748685

result:

ok 1 number(s): "250748685"

Test #8:

score: 0
Accepted
time: 1ms
memory: 4136kb

input:

39 2 38

output:

624060592

result:

ok 1 number(s): "624060592"

Test #9:

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

input:

40 18 22

output:

739993796

result:

ok 1 number(s): "739993796"

Test #10:

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

input:

40 11 35


output:

135213497

result:

ok 1 number(s): "135213497"

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 0
Time Limit Exceeded

input:

199 100 70

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%