Submission #34239733
Source Code Expand
Copy
#include <bits/stdc++.h>#define P pair<int, int>#define fi first#define se second#define pb push_back#define all(v) v.begin(), v.end()using namespace std;template <typename T> void rd(T &x) {x = 0; T f = 1; char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}x *= f;}template <typename T> void write(T x) {if (x < 0) {putchar('-'); x = -x;}if (x >= 10) write(x / 10);putchar(x % 10 + 48);}typedef long long ll;const int N = 110;
#include <bits/stdc++.h> #define P pair<int, int> #define fi first #define se second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; template <typename T> void rd(T &x) { x = 0; T f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } template <typename T> void write(T x) { if (x < 0) {putchar('-'); x = -x;} if (x >= 10) write(x / 10); putchar(x % 10 + 48); } typedef long long ll; const int N = 110; const int M = 1e3 + 10; const int INF = 0x3f3f3f3f; const ll Mod = 998244353; int n, D; int p[N], q[N]; ll f[2][M][M]; int main() { rd(n); rd(D); for (int i = 1; i <= n; i++) rd(p[i]); for (int i = 1; i <= n; i++) rd(q[i]); int flag = 0; f[flag][0][0] = 1; for (int i = 1; i <= n; i++) { flag ^= 1; for (int j = 0; j <= D; j++) for (int k = 0; k <= D; k++) f[flag][j][k] = 0; int r = min(p[i], q[i]) + D, l = max(p[i], q[i]) - D; if (r < l) { puts("0"); return 0; } else { for (int x = l; x <= r; x++) { for (int j = abs(p[i] - x); j <= D; j++) { for (int k = abs(q[i] - x); k <= D; k++) { f[flag][j][k] = (f[flag ^ 1][j - abs(p[i] - x)][k - abs(q[i] - x)] + f[flag][j][k]) % Mod; } } } } } ll ans = 0; for (int i = 0; i <= D; i++) { for (int j = 0; j <= D; j++) { ans = (ans + f[flag][i][j]) % Mod; } } write(ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Manhattan Cafe |
User | LYR_ |
Language | C++ (GCC 9.2.1) |
Score | 0 |
Code Size | 1766 Byte |
Status | TLE |
Exec Time | 6616 ms |
Memory | 19356 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
All | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 02_corner_00.txt, 02_corner_01.txt, 02_corner_02.txt, 02_corner_03.txt, 02_corner_04.txt, 02_corner_05.txt, 02_corner_06.txt, 02_corner_07.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00.txt | AC | 5 ms | 3524 KB |
00_sample_01.txt | AC | 3 ms | 3552 KB |
00_sample_02.txt | AC | 18 ms | 4532 KB |
01_random_00.txt | AC | 4507 ms | 11036 KB |
01_random_01.txt | TLE | 6616 ms | 13692 KB |
01_random_02.txt | AC | 305 ms | 7516 KB |
01_random_03.txt | AC | 120 ms | 7788 KB |
01_random_04.txt | AC | 5316 ms | 13364 KB |
01_random_05.txt | TLE | 6616 ms | 18504 KB |
01_random_06.txt | AC | 775 ms | 6524 KB |
01_random_07.txt | TLE | 6616 ms | 11904 KB |
01_random_08.txt | AC | 5941 ms | 11044 KB |
01_random_09.txt | AC | 34 ms | 4240 KB |
01_random_10.txt | AC | 63 ms | 4404 KB |
01_random_11.txt | TLE | 6616 ms | 18992 KB |
01_random_12.txt | TLE | 6616 ms | 19004 KB |
01_random_13.txt | TLE | 6616 ms | 19004 KB |
01_random_14.txt | TLE | 6616 ms | 19008 KB |
02_corner_00.txt | TLE | 6616 ms | 18996 KB |
02_corner_01.txt | AC | 45 ms | 19356 KB |
02_corner_02.txt | AC | 39 ms | 19332 KB |
02_corner_03.txt | TLE | 6616 ms | 18992 KB |
02_corner_04.txt | AC | 984 ms | 11432 KB |
02_corner_05.txt | AC | 15 ms | 11368 KB |
02_corner_06.txt | AC | 14 ms | 11404 KB |
02_corner_07.txt | AC | 984 ms | 11468 KB |