QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125744#5087. Shuffle GamePetroTarnavskyi#WA 3ms5540kbC++171.4kb2023-07-17 15:10:332023-07-17 15:10:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 15:10:35]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5540kb
  • [2023-07-17 15:10:33]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int INF = 1e9;
const int MAX = 1 << 9;

void upd(int& x, int val) {
	x = max(x, val);
}

int dp[MAX][MAX], ndp[MAX][MAX];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, p, q;
	cin >> n >> p >> q;
	vector<string> x(n), p1(p), p2(q);
	for (string& xi : x) {
		cin >> xi;
	}
	for (string& pi : p1) {
		cin >> pi;
	}
	for (string& pi : p2) {
		cin >> pi;
	}
	FOR(i, 0, MAX) {
		FOR(j, 0, MAX) {
			dp[i][j] = ndp[i][j] = -INF;
		}
	}
	dp[0][0] = ndp[0][0] = 0;
	FOR(i, 0, n) {
		FOR(j, 0, p + 1) {
			FOR(k, 0, q + 1) {
				upd(ndp[j][k], dp[j][k]);
				if (j < p) {
					if (x[i] == p1[j]) {
						upd(ndp[j + 1][k], dp[j][k] + 1);
					}
					upd(dp[j + 1][k], dp[j][k]);
				}
				if (k < q) {
					if (x[i] == p2[k]) {
						upd(ndp[j][k + 1], dp[j][k] + 1);
					}
					upd(dp[j][k + 1], dp[j][k]);
				}
			}
		}
		memcpy(dp, ndp, sizeof dp);
	}
	cout << dp[p][q] << "\n";
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5404kb

input:

5 2 3
CJ D5 HA C2 S7
D5 HA
CJ S7 C2

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5500kb

input:

6 3 3
C9 HK SQ SQ H2 CA
CA HK SQ
H2 C9 SQ

output:

4

result:

ok single line: '4'

Test #3:

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

input:

7 3 4
S9 C10 DJ S6 S7 SA DQ
DJ S6 S7
S9 C10 SA DQ

output:

7

result:

ok single line: '7'

Test #4:

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

input:

10 1 9
CJ CJ CJ CJ CJ CJ CJ CJ CJ CJ
CJ
CJ CJ CJ CJ CJ CJ CJ CJ CJ

output:

10

result:

ok single line: '10'

Test #5:

score: 0
Accepted
time: 3ms
memory: 5416kb

input:

10 4 6
D2 D2 D2 D2 D2 D2 D2 D2 D2 D2
D2 D2 D2 D2
D2 D2 D2 D2 D2 D2

output:

10

result:

ok single line: '10'

Test #6:

score: 0
Accepted
time: 3ms
memory: 5412kb

input:

10 3 7
C7 C9 S6 C8 SK C3 DJ S7 H4 CA
S6 C8 C3
C7 C9 SK DJ S7 H4 CA

output:

10

result:

ok single line: '10'

Test #7:

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

input:

10 8 2
HQ H2 C10 D5 C5 C6 C6 S4 DJ D8
HQ H2 C10 D5 C5 C6 S4 DJ
C6 D8

output:

10

result:

ok single line: '10'

Test #8:

score: 0
Accepted
time: 3ms
memory: 5484kb

input:

10 9 1
H10 D8 HA H3 H3 HK DA HQ DJ SK
SK DJ HQ DA HK H3 H3 HA D8
H10

output:

3

result:

ok single line: '3'

Test #9:

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

input:

10 9 1
C9 HJ SJ SK D5 H9 HA HK DJ C6
C6 DJ HK HA H9 D5 SK SJ C9
HJ

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 3ms
memory: 5408kb

input:

20 1 19
HQ D4 S10 C10 C6 C10 S8 D10 D10 C9 C6 D7 CQ HQ H7 C5 HQ S2 S6 C4
CQ
C10 HQ C9 S6 C4 D10 D10 S8 D4 C5 C10 H7 HQ C6 HQ S10 S2 D7 C6

output:

7

result:

ok single line: '7'

Test #11:

score: 0
Accepted
time: 3ms
memory: 5504kb

input:

20 10 10
D7 SJ DA CA C7 SK H10 CK D8 DQ D2 DJ H10 C7 C5 HJ CQ S4 DK H3
SK DQ SJ CQ DK S4 C7 C7 CK CA
D2 D8 DA H10 DJ C5 HJ H10 D7 H3

output:

10

result:

ok single line: '10'

Test #12:

score: -100
Wrong Answer
time: 3ms
memory: 5540kb

input:

20 15 5
SJ CK D5 S10 H5 D8 H8 C5 SQ C10 D10 CA DQ H7 C3 H10 C7 SJ S10 D8
SJ D5 D8 H10 C3 C7 S10 H5 H8 DQ D8 SJ CK SQ H7
S10 C10 C5 D10 CA

output:

10

result:

wrong answer 1st lines differ - expected: '11', found: '10'