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;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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
AC × 3
AC × 17
TLE × 9
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


2025-02-28 (Fri)
05:20:24 +00:00