QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371703#8049. Equal SumsCreditML 1ms3876kbC++171.6kb2024-03-30 15:03:502024-03-30 15:03:57

Judging History

你现在查看的是最新测评结果

  • [2024-03-30 15:03:57]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3876kb
  • [2024-03-30 15:03:50]
  • 提交

answer


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int mod = 998244353;
int k, e, n;
ll dp[505][505][1005];
ll lx[505], ly[505], rx[505], ry[505];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> lx[i] >> rx[i];
    }
    for (int i = 1;i <= m;i++) {
        cin >> ly[i] >> ry[i];
    }

    for (int i = 0;i <= n;i++) {
        for (int j = 0;j <= m;j++) {
            for (int k = 1;k <= 1000;k++) {
                dp[i][j][k] += dp[i][j][k - 1] %mod;
            }
            dp[0][0][500] = 1;
            for (int k = 0;k <= 1000;k++) {
                if (k <= 500) {
                    dp[i + 1][j][k + lx[i + 1]] += dp[i][j][k];
                    dp[i + 1][j][k + rx[i + 1] + 1] -= (dp[i][j][k] - mod);
                    dp[i + 1][j][k + lx[i + 1]] %= mod;
                    dp[i + 1][j][k + lx[i + 1] + 1] %= mod;
                }
                else {
                    dp[i][j + 1][k - ry[j + 1]] += dp[i][j][k] ;
                    dp[i][j + 1][k - ly[j + 1] + 1] -= (dp[i][j][k] - mod);
                    dp[i][j + 1][k - ry[j + 1]] %= mod;
                    dp[i][j + 1][k - ry[j + 1] + 1] %= mod;
                }
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << dp[i][j][500] % mod << " ";
        }
        cout << endl;
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3876kb

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
Memory 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 -817663288 -14021235 586589234 293043270 404363796 865361724 -332756365 -879405547 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...

result: