QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485502#4931. Comic BingePetroTarnavskyi#WA 0ms3720kbC++202.8kb2024-07-20 18:50:272024-07-20 18:50:27

Judging History

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

  • [2024-07-20 18:50:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3720kb
  • [2024-07-20 18:50:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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

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

const LL LINF = 4e12 + 7;
const int N = 104;
const int mod = 998244353;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
	return (LL)a * b % mod;
}
int binpow(int a, int n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

int fact[N], ifact[N];
int C(int n, int k)
{
	if(k < 0 || k > n)
		return 0;
	return mult(fact[n], mult(ifact[k], ifact[n - k]));
}

void init()
{
	fact[0] = 1;
	FOR(i, 1, N)
		fact[i] = mult(fact[i - 1], i);
	ifact[N - 1] = binpow(fact[N - 1], mod - 2);
	RFOR(i, N, 1)
		ifact[i - 1] = mult(ifact[i], i);
	
}



int dpT[N][N][2][2][N];



VI all;

int dp(int L, int R, int cl, int cr, int cntRed)
{
	if (L + 1 == R)
		return cntRed == 0;
	if (cntRed > R - L - 1)
		return 0;
	if (dpT[L][R][cl][cr][cntRed] != -1)
		return dpT[L][R][cl][cr][cntRed];
	int res = 0;
	
	FOR (i, L + 1, R)
	{
		int col = all[i] - all[L] <= all[R] - all[i] ? cl : cr;
		int cntR = cntRed - col;
		FOR (cntRL, 0, cntR + 1)
		{
			res = add(res, mult(mult(dp(L, i, cl, col, cntRL), dp(i, R, col, cr, cntR - cntRL)), C(R - L - 2, i - L - 1)));
		}
	}
	return dpT[L][R][cl][cr][cntRed] = res;
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	init();
	
	int n, m;
	cin >> n >> m;
	
	vector<PII> pos(n);
	FOR (i, 0, n)
	{
		cin >> pos[i].F;
		string s;
		cin >> s;
		if (s == "RED")
			pos[i].S = 1;
	}
	pos.PB({-LINF, 0});
	pos.PB({LINF, 1});
	sort(ALL(pos));
	
	FOR (i, 0, SZ(pos))
		all.PB(pos[i].F);
	FOR (i, 0, m)
	{
		int x;
		cin >> x;
		all.PB(x);
	}
	sort(ALL(all));
	VI idx(n + 2);
	FOR (i, 0, n + 2)
		idx[i] = lower_bound(ALL(all), pos[i].F) - all.begin();
		
	VI ans(N);
	ans[0] = 1;
	FOR (it, 0, n + 1)
	{
		int i1 = idx[it];
		int i2 = idx[it + 1];
		VI ans2 = ans;
		FOR (red, 0, m + 1)
		{
			FOR (curRed, 0, m + 1)
			{
				ans2[red + curRed] = add(ans2[red + curRed], mult(ans[red], dp(i1, i2, pos[it].S, pos[it + 1].S, curRed)));
			}
		}
		ans = ans2;
	}
	int cntB = 0, cntR = 0;
	FOR (i, 0, n + 2)
	{
		if (pos[i].S == 0)
			cntB++;
		else
			cntR++;
	}
	int res = 0;
	FOR (red, 0, m + 1)
	{
		if (cntR + red > cntB + m - red)
			res = add(res, ans[red]);
	}
	cout << res << '\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3720kb

input:

6
3 1 1 1 1 2
1 5 3 3 7 4

output:

0

result:

wrong answer 1st lines differ - expected: '13', found: '0'