QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674028#2998. 皮配propane80 1568ms28240kbC++206.0kb2024-10-25 13:15:472024-10-25 13:15:47

Judging History

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

  • [2024-10-25 13:15:47]
  • 评测
  • 测评结果：80
  • 用时：1568ms
  • 内存：28240kb
查看
  • [2024-10-25 13:15:47]
  • 提交

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 s[2505][2505];

int get(int x1, int y1, int x2, int y2){
    if (x1 > x2 or y1 > y2) return 0;
    int ans = s[x2][y2];
    if (x1 - 1 >= 0) sub(ans, s[x1 - 1][y2]);
    if (y1 - 1 >= 0) sub(ans, s[x2][y1 - 1]);
    if (x1 - 1 >= 0 and y1 - 0 >= 0) add(ans, s[x1 - 1][y1 - 1]);
    return ans;
}

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<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);
        }
        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;
        }
        int sum = 0;
        vector<vector<int> > dp(1, vector<int>(1));
        dp[0][0] = 1;
        vector<int> f1(1), f2(1);
        f1[0] = f2[0] = 1;
        int sum2 = 0;
        for(int i = 1; i <= c; i++){
            if (pos[i].empty()) continue;
            if (st[i]){
                int t = 0;
                for(auto id : pos[i]){
                    t += p[id].second;
                }
                vector<vector<int> > ndp(min(sum + t, m) + 1, vector<int>(min(sum + t, m) + 1));
                // 选择阵营0
                {
                    int cur = 0; 
                    vector<int> f(1);
                    f[0] = 1;
                    for(auto id : pos[i]){
                        int k = p[id].second;
                        vector<int> nf(min(cur + k, m) + 1);
                        for(int j = 0; j < f.size(); j++){
                            if (v[id] != 0 and j + k < nf.size()) add(nf[j + k], f[j]);
                            if (v[id] != 1) add(nf[j], f[j]);
                        }
                        f.swap(nf);
                        cur += k;
                    }
                    for(int j = 0; j < f.size(); j++){
                        for(int a = 0; a + cur < ndp.size() and a < dp.size(); a++){
                            for(int b = 0; b + j < ndp[0].size() and b < dp[0].size(); b++){
                                add(ndp[a + cur][b + j], mul(dp[a][b], f[j]));
                            }
                        }
                    }
                }
                // 选择阵营1
                {
                    int cur = 0; 
                    vector<int> f(1);
                    f[0] = 1;
                    for(auto id : pos[i]){
                        int k = p[id].second;
                        vector<int> nf(min(cur + k, m) + 1);
                        for(int j = 0; j < f.size(); j++){
                            if (v[id] != 2 and j + k < nf.size()) add(nf[j + k], f[j]);
                            if (v[id] != 3) add(nf[j], f[j]);
                        }
                        f.swap(nf);
                        cur += k;
                    }
                    for(int j = 0; j < f.size(); j++){
                        for(int a = 0; a < dp.size(); a++){
                            for(int b = 0; b + j < ndp[0].size() and b < dp[0].size(); b++){
                                add(ndp[a][b + j], mul(dp[a][b], f[j]));
                            }
                        }
                    }
                }
                dp.swap(ndp);
                sum += t;
            }
            else{
                int t = 0;
                for(auto id : pos[i]){
                    t += p[id].second;
                }
                {
                    vector<int> nf1(min(sum2 + t, m) + 1);
                    for(int j = 0; j < f1.size(); j++){
                        add(nf1[j], f1[j]);
                        if (j + t < nf1.size()) add(nf1[j + t], f1[j]);
                    }
                    f1.swap(nf1);
                }
                for(auto id : pos[i]){
                    int k = p[id].second;
                    vector<int> nf2(min(sum2 + k, m) + 1);
                    for(int j = 0; j < f2.size(); j++){
                        add(nf2[j], f2[j]);
                        if (j + k < nf2.size()) add(nf2[j + k], f2[j]);
                    }
                    f2.swap(nf2);
                    sum2 += k;
                }
            }
        }
        for(int i = 0; i < f1.size(); i++){
            for(int j = 0; j < f2.size(); j++){
                s[i][j] = mul(f1[i], f2[j]);
                if (i - 1 >= 0) add(s[i][j], s[i - 1][j]);
                if (j - 1 >= 0) add(s[i][j], s[i][j - 1]);
                if (i - 1 >= 0 and j - 1 >= 0) sub(s[i][j], s[i - 1][j - 1]);
            }
        }
        int tot = sum + sum2;
        int ans = 0;
        for(int i = 0; i < dp.size(); i++){
            for(int j = 0; j < dp[0].size(); j++){
                // i + a \in [tot - c1, c0]
                // j + b \in [tot - d1, d0]
                int l1 = max(0, tot - c1 - i);
                int r1 = min(int(f1.size()) - 1, c0 - i);
                int l2 = max(0, tot - d1 - j);
                int r2 = min(int(f2.size()) - 1, d0 - j);
                add(ans, mul(dp[i][j], get(l1, l2, r1, 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: 0ms
memory: 3600kb

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: 5ms
memory: 4028kb

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: 0ms
memory: 3980kb

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: 5896kb

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: 56ms
memory: 6508kb

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: 22ms
memory: 13320kb

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: 0
Time Limit Exceeded

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:

result:

Test #8:

score: 10
Accepted
time: 1568ms
memory: 22104kb

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: 125ms
memory: 28240kb

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: 0
Time Limit Exceeded

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:

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 10:02:27 | OpenSource Project