QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674274#2998. 皮配propane100 ✓676ms15780kbC++204.8kb2024-10-25 14:53:322024-10-25 14:53:33

Judging History

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

  • [2024-10-25 14:53:33]
  • 评测
  • 测评结果：100
  • 用时：676ms
  • 内存：15780kb
查看
  • [2024-10-25 14:53:32]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;
const int mod = 998244353;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

int f[2505], g[2505];
int dp[2505][30 * 10 + 5][2], ndp[2505][30 * 10 + 5][2];

int get(int s[], int l, int r){
    if (l > r) return 0;
    return s[r] - (l == 0 ? 0 : s[l - 1]) + mod;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, c;
        cin >> n >> c;
        int c0, c1, d0, d1;
        cin >> c0 >> c1 >> d0 >> d1;
        const int m = max({c0, c1, d0, d1});
        vector<vector<int> > pos(c + 1);
        vector<int> s(c + 1);
        vector<pair<int, int> > p(n);
        vector<bool> st(c + 1);
        for(int i = 0; i < n; i++){
            cin >> p[i].first >> p[i].second;
            pos[p[i].first].push_back(i);
            s[p[i].first] += p[i].second;
        }
        int k;
        cin >> k;
        vector<pair<int, int> > q(k);
        vector<int> v(n, -1);
        for(int i = 0; i < k; i++){
            int a, b;
            cin >> a >> b;
            a--;
            v[a] = b;
            st[p[a].first] = true;
        }
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        f[0] = g[0] = 1;
        for(int i = 1; i <= c; i++){
            if (!st[i] and s[i] > 0){
                for(int j = m; j >= s[i]; j--){
                    add(f[j], f[j - s[i]]);
                }
            }
        }
        for(int i = 0; i < n; i++){
            if (v[i] == -1){
                int w = p[i].second;
                for(int j = m; j >= w; j--){
                    add(g[j], g[j - w]);
                }
            }
        }
        for(int i = 1; i <= m; i++){
            add(f[i], f[i - 1]);
            add(g[i], g[i - 1]);
        }
        const int sz = min(k * 10, m);
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= sz; j++){
                dp[i][j][0] = dp[i][j][1] = 0;
            }
        }
        dp[0][0][0] = 1;
        for(int i = 1; i <= c; i++){
            if (!st[i]) continue;
            for(int a = 0; a <= m; a++){
                for(int b = 0; b <= sz; b++){
                    ndp[a][b][0] = ndp[a][b][1] = 0;
                }
            }
            for(int a = 0; a <= m; a++){
                for(int b = 0; b <= sz; b++){
                    int t = (dp[a][b][0] + dp[a][b][1]) % mod;
                    if (a + s[i] <= m) add(ndp[a + s[i]][b][0], t);
                    add(ndp[a][b][1], t);
                }
            }
            swap(dp, ndp);
            for(auto id : pos[i]){
                if (v[id] == -1) continue;
                int k = p[id].second;
                for(int a = 0; a <= m; a++){
                    for(int b = 0; b <= sz; b++){
                        ndp[a][b][0] = ndp[a][b][1] = 0;
                    }
                }
                for(int a = 0; a <= m; a++){
                    for(int b = 0; b <= sz; b++){
                        if (v[id] != 0 and b + k <= sz){
                            add(ndp[a][b + k][0], dp[a][b][0]);
                        }
                        if (v[id] != 1){
                            add(ndp[a][b][0], dp[a][b][0]);
                        }
                        if (v[id] != 2 and b + k <= sz){
                            add(ndp[a][b + k][1], dp[a][b][1]);
                        }
                        if (v[id] != 3){
                            add(ndp[a][b][1], dp[a][b][1]);
                        }
                    }
                }
                for(int i = 0; i <= m; i++){
                    for(int j = 0; j <= sz; j++){
                        dp[i][j][0] = ndp[i][j][0];
                        dp[i][j][1] = ndp[i][j][1];
                    }
                }
            }
        }
        int tot = 0;
        for(int i = 1; i <= c; i++) tot += s[i];
        int ans = 0;
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= sz; j++){
                int t = (dp[i][j][0] + dp[i][j][1]) % mod;
                // [tot - c1, c0]
                // [tot - d1, d0]
                int l1 = max(0, tot - c1 - i);
                int r1 = min(m, c0 - i);
                int l2 = max(0, tot - d1 - j);
                int r2 = min(m, d0 - j);
                add(ans, mul(t, mul(get(f, l1, r1), get(g, l2, r2))));
            }
        }
        cout << ans << '\n';
    }

}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 6ms
memory: 15568kb

input:

5
1 1
1 1 1 1
1 1
1
1 0
1 1
1 1 1 1
1 1
0
1 1
1 1 1 1
1 1
1
1 1
1 1
1 1 1 1
1 1
1
1 2
1 1
1 1 1 1
1 1
1
1 3

output:

3
4
3
3
3

result:

ok 5 lines

Test #2:

score: 10
Accepted
time: 24ms
memory: 15568kb

input:

5
10 10
100 100 100 100
2 9
7 10
3 10
3 10
6 10
4 10
2 10
6 10
1 10
10 10
10
7 0
8 3
5 1
4 2
6 1
3 0
1 2
10 0
2 1
9 2
10 10
100 100 100 99
6 10
7 10
5 10
5 10
10 10
5 10
2 9
3 6
7 10
3 10
5
10 2
6 3
4 2
7 0
3 1
10 10
96 100 100 8
3 10
9 10
2 10
3 10
3 10
2 10
3 8
9 5
2 10
3 10
5
9 3
10 1
8 0
1 1
6 2...

output:

5184
13824
8
7768
59049

result:

ok 5 lines

Test #3:

score: 10
Accepted
time: 1ms
memory: 5548kb

input:

5
20 20
93 93 100 97
6 3
19 7
6 10
2 7
5 6
11 7
4 10
17 10
1 7
19 4
14 5
20 7
15 3
6 7
5 6
15 10
3 7
5 10
15 6
1 7
0
20 20
100 100 100 100
20 10
7 9
2 8
5 10
4 6
1 10
4 10
17 10
1 6
5 10
12 10
9 6
12 8
1 10
10 10
13 10
12 10
10 10
13 7
18 10
0
20 20
98 96 100 10
3 5
8 5
19 7
3 6
19 5
3 6
5 4
6 5
6 3...

output:

826806650
477561084
85170
0
131405274

result:

ok 5 lines

Test #4:

score: 10
Accepted
time: 1ms
memory: 5596kb

input:

5
30 30
100 98 94 97
12 2
27 5
25 5
24 4
14 5
4 6
22 7
2 3
30 8
1 2
7 5
2 2
20 5
11 7
15 5
18 3
11 3
1 4
25 5
11 2
15 4
12 5
3 8
12 7
6 3
30 8
19 5
13 3
21 9
4 3
0
30 30
93 99 92 93
24 3
23 10
17 5
22 5
17 7
29 10
18 6
7 5
17 6
9 7
3 6
16 6
9 5
10 4
6 5
20 6
2 7
20 5
3 3
9 3
2 5
29 6
9 8
1 4
12 5
1 ...

output:

217399345
840927688
15230976
0
991268888

result:

ok 5 lines

Test #5:

score: 10
Accepted
time: 80ms
memory: 15484kb

input:

5
30 30
482 500 500 500
17 10
15 10
25 10
14 8
9 10
1 10
15 10
23 10
13 8
15 9
15 8
20 10
19 10
6 10
18 8
23 10
3 10
28 10
13 10
2 10
15 10
17 10
1 10
2 10
14 10
11 10
29 7
24 10
14 10
30 10
13
15 3
25 3
18 2
23 2
1 3
7 0
4 2
20 0
26 2
9 1
3 2
30 2
24 1
30 30
485 500 500 489
22 10
7 10
10 10
1 8
9 1...

output:

335527780
562018873
0
721419962
437550714

result:

ok 5 lines

Test #6:

score: 10
Accepted
time: 0ms
memory: 9732kb

input:

5
500 500
998 974 1000 975
427 4
84 3
313 2
161 4
371 2
481 4
5 3
80 2
156 6
448 4
424 2
302 1
277 1
14 2
343 6
431 2
452 3
369 3
427 2
245 6
413 3
317 3
1 3
447 1
337 4
181 2
224 5
243 3
494 2
248 3
152 5
430 4
119 4
290 2
19 3
93 2
274 4
14 2
67 2
56 2
75 5
454 3
407 1
324 3
138 5
283 4
274 4
472 ...

output:

444961978
726306306
604706636
0
591791292

result:

ok 5 lines

Test #7:

score: 10
Accepted
time: 277ms
memory: 15724kb

input:

5
500 30
1000 982 976 986
1 2
23 3
22 1
5 6
22 4
27 2
22 5
18 6
19 1
11 4
30 2
20 4
2 3
18 2
2 3
18 4
8 2
27 4
3 3
27 4
19 5
2 1
28 4
18 2
10 1
11 4
29 3
20 2
22 3
4 2
4 4
26 3
3 3
3 4
3 5
18 3
3 1
4 3
11 3
15 6
19 2
21 3
23 4
12 2
14 4
2 1
30 2
15 4
10 3
21 3
12 6
11 3
14 2
5 2
30 1
11 2
25 4
13 2
...

output:

721598186
376511045
916295431
692157069
839818974

result:

ok 5 lines

Test #8:

score: 10
Accepted
time: 327ms
memory: 15780kb

input:

5
500 500
975 1000 1000 1000
322 4
4 1
327 6
287 3
352 3
493 3
8 4
89 1
348 3
277 2
158 2
375 2
457 3
155 2
94 2
423 2
407 4
405 2
474 4
44 2
103 3
430 4
61 2
83 2
314 2
143 5
468 2
481 3
241 2
388 4
453 3
301 3
225 4
375 2
181 5
259 5
220 4
126 3
301 4
150 1
383 1
394 3
177 1
329 4
448 1
394 3
129 ...

output:

139292860
233441301
292203931
490172452
532521263

result:

ok 5 lines

Test #9:

score: 10
Accepted
time: 14ms
memory: 10992kb

input:

5
1000 1000
2500 2500 2500 2500
285 3
51 3
740 5
140 4
758 4
740 2
493 7
155 3
30 6
380 2
235 3
447 5
500 4
402 2
358 2
936 4
48 4
793 4
994 1
668 5
607 3
694 4
426 4
377 7
314 7
83 7
948 3
423 6
229 4
920 3
498 5
262 3
22 4
25 3
661 4
420 2
689 5
509 5
401 3
213 4
286 4
699 3
466 4
430 3
734 4
420 ...

output:

803471990
878872778
65626616
0
143791691

result:

ok 5 lines

Test #10:

score: 10
Accepted
time: 676ms
memory: 15636kb

input:

5
1000 1000
2500 2500 2500 2500
801 5
102 2
581 5
589 5
493 6
214 2
604 10
391 3
7 2
555 4
594 3
614 8
230 5
900 4
605 5
869 6
991 4
820 2
124 4
630 2
694 3
244 6
170 4
8 2
360 1
394 3
512 7
823 3
89 3
988 5
433 4
858 6
362 4
995 4
181 3
718 3
275 2
325 4
11 4
5 2
222 4
209 5
562 1
158 2
908 3
496 3...

output:

517838564
14120732
890567148
196568551
60485305

result:

ok 5 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-02 06:33:37 | OpenSource Project