QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485502 | #4931. Comic Binge | PetroTarnavskyi# | WA | 0ms | 3720kb | C++20 | 2.8kb | 2024-07-20 18:50:27 | 2024-07-20 18:50:27 |
Judging History
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'