QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #482071 | #8049. Equal Sums | liangbowen | TL | 2ms | 8292kb | C++14 | 1.3kb | 2024-07-17 17:06:24 | 2024-07-17 17:06:25 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define mems(x, v) memset(x, v, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double wisdom;
const int N = 505, mod = 998244353;
int lx[N], ly[N], rx[N], ry[N], dp[2][N][N << 1], sum[2][N][N << 1]; //dp[i][j][k]: 选了i个A, j个B, sigma(xi)-sigma(yi)=k, 方案数
#define DP(i, j, k) dp[(i) & 1][j][k + 500]
#define S(i, j, k) sum[(i) & 1][j][k + 500]
int main() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d%d", &lx[i], &rx[i]);
for (int i = 1; i <= m; i++) scanf("%d%d", &ly[i], &ry[i]);
DP(0, 0, 0) = 1; for (int i = -500; i <= 500; i++) S(0, 0, i) = (S(0, 0, i - 1) + DP(0, 0, i)) % mod;
for (int i = 0; i <= n; i++, i == 0 ? 1 : puts("")) for (int j = 0; j <= m; j++) {
mems(dp[i & 1], 0);
if (i) for (int k = 0; k <= 500; k++) DP(i, j, k) = (S(i - 1, j, k - lx[i]) - S(i - 1, j, k - rx[i] - 1) + mod) % mod;
if (j) for (int k = -500; k <= 0; k++) DP(i, j, k) = (S(i, j - 1, k + ry[j]) - S(i, j - 1, k + ly[j] - 1) + mod) % mod;
if (i || j) for (int k = -500; k <= 500; k++) S(i, j, k) = (S(i, j, k - 1) + DP(i, j, k)) % mod;
if (i && j) printf("%d ", DP(i, j, 0));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8292kb
input:
2 3 1 2 2 3 1 4 2 2 1 3
output:
2 0 0 3 4 4
result:
ok 6 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
500 500 19 458 1 480 7 485 50 461 12 476 15 461 48 466 40 453 46 467 9 458 27 478 26 472 46 459 29 490 6 500 17 487 48 484 28 472 28 459 25 480 4 491 29 481 36 460 2 491 44 499 22 473 20 458 4 483 27 471 2 496 11 461 43 450 2 478 37 466 15 459 42 482 7 451 19 455 2 453 47 475 48 450 1 474 46 471 9 4...
output:
411 79401 9145270 673005095 180581065 984223118 586589234 293043270 404363796 865361724 665487988 118838806 926189944 226338288 521479857 808644951 786041288 340769021 177100 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...