Submission #25500654

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long

template <typename T>
void read (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 << 3) + (x << 1) + ch - '0';
        ch = getchar ();
    }
    x *= f;
}

const int Maxn = 5000;
const LL Mod = 998244353;

LL dp[Maxn + 5], pre[Maxn + 5];

int n;
struct Node {
    int x, y;
}a[Maxn + 5];
bool cmp (Node x, Node y) {
    return x.x < y.x;
}

int main () {
    read (n);
    for (int i = 1; i <= n; i++) {
        read (a[i].x); 
    }
    for (int i = 1; i <= n; i++) {
        read (a[i].y);
    }
    sort (a + 1, a + 1 + n, cmp);
    
    dp[0] = 1; for (int i = 0; i <= Maxn; i++) pre[i] = 1;
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].x >= a[i].y)
            ans = (ans + pre[a[i].x - a[i].y]) % Mod;
        
        for (int j = Maxn; j >= a[i].y; j--) {
            dp[j] = (dp[j] + dp[j - a[i].y]) % Mod;
        }
        for (int j = 0; j <= Maxn; j++) {
            if (j == 0) pre[j] = dp[j];
            else pre[j] = (pre[j - 1] + dp[j]) % Mod;
        }
        // printf ("--------\n");
        // printf ("i = %d\n", i);
        // for (int j = 1; j <= 10; j++) {
        //     printf ("    dp[%d] = %lld\n", j, dp[j]);
        // }
    }
    printf ("%lld", ans);
    return 0;
}

Submission Info

Judge Result