QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#608596	#2998. 皮配	Lackofgod	10	354ms	124104kb	C++14	4.3kb	2024-10-03 23:31:10	2024-10-03 23:31:15

Judging History

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

[2024-10-03 23:31:15]
评测

测评结果：10
用时：354ms
内存：124104kb

查看

[2024-10-03 23:31:10]
提交

answer

#include <bits/stdc++.h>
#define forn(i,aa,bb) for(int i=aa;i<=bb;++i)
#define LL long long 
#define pii pair<int,int>
#define int long long 
using namespace std;
const int N=3e3+5;
const LL mod=998244353;
int n,c;
int f[2][N][N];
int f1[N],g1[N];
vector<int> G[N];
int b[N],h[N]; 
int C1,C0,D1,D0;
int tot=0;
int now,pre;
void clear() {
    tot=min(max({C0,C1,D0,D1}),tot);
    forn(i,0,1)
        forn(j,0,tot)
            forn(k,0,tot) 
                f[i][j][k]=0;
    forn(i,0,tot) {
        G[i].clear();
        b[i]=0;
        h[i]=0;
        f1[i]=g1[i]=0;
    }
}
void solve_no_hate() {
    f1[0]=1ll; g1[0]=1ll;
    forn(i,1,c) {
        if (G[i].empty()) continue;
        int sum1=0;
        //check 
        bool fl=0;
        for(int x:G[i]) { 
            if (h[x]) {
                fl=1;
                break;
            }
            sum1+=b[x];
        }

        //solve_zhenying
        if (!fl) {
            for(int j=tot-sum1;j>=0;--j)
                f1[j+sum1]=(f1[j+sum1]+f1[j])%mod;
        }

        //solve_paixi
        for(int x:G[i]) {
            if (h[x]) continue;
            for(int j=tot-b[x];j>=0;--j)
                g1[j+b[x]]=(g1[j+b[x]]+g1[j])%mod;
        }
    }
    forn(i,1,tot)  {
        f1[i]=(f1[i]+f1[i-1])%mod;
        g1[i]=(g1[i]+g1[i-1])%mod;
    }
}
void solve_hate() {
    now=0; pre=1;
    int maxm=0;
    f[0][0][0]=1ll;
    forn(i,1,c) {
        if (G[i].empty()) continue;
        int sum1=0;
        //check 
        bool fl=0;
        for(int x:G[i]) {
            if (h[x]) fl=1;
            sum1+=b[x];
        }
        if (!fl) continue;

        swap(now,pre);
        for(int x:G[i]) {
            if (!h[x]) continue;
            forn(j,0,tot)
                forn(k,0,maxm)
                    f[now][j][k]=0;
            for(int j=tot;j>=0;--j)
                for(int k=maxm;k>=0;--k) {
                    if (h[x]==1) {
                        if (j+sum1<=tot) f[now][j+sum1][k]=(f[now][j+sum1][k]+f[pre][j][k])%mod;
                        if (k+b[x]<=tot) f[now][j][k+b[x]]=(f[now][j][k+b[x]]+f[pre][j][k])%mod;
                        f[now][j][k]=(f[now][j][k]+f[pre][j][k])%mod;
                    }
                    if (h[x]==2) {
                        if (j+sum1<=tot && k+b[x]<=tot) f[now][j+sum1][k+b[x]]=(f[now][j+sum1][k+b[x]]+f[pre][j][k])%mod;
                        if (k+b[x]<=tot) f[now][j][k+b[x]]=(f[now][j][k+b[x]]+f[pre][j][k])%mod;
                        f[now][j][k]=(f[now][j][k]+f[pre][j][k])%mod;
                    }
                    if (h[x]==3) {
                        f[now][j][k]=(f[now][j][k]+f[pre][j][k])%mod;
                        if (j+sum1<=tot && k+b[x]<=tot) f[now][j+sum1][k+b[x]]=(f[now][j+sum1][k+b[x]]+f[pre][j][k])%mod;
                        if (j+sum1<=tot) f[now][j+sum1][k]=(f[now][j+sum1][k]+f[pre][j][k])%mod;
                    }
                    if (h[x]==4) {
                        f[now][j][k+b[x]]=(f[now][j][k+b[x]]+f[pre][j][k])%mod;
                        if (j+sum1<=tot && k+b[x]<=tot) f[now][j+sum1][k+b[x]]=(f[now][j+sum1][k+b[x]]+f[pre][j][k])%mod;
                        if (j+sum1<=tot) f[now][j+sum1][k]=(f[now][j+sum1][k]+f[pre][j][k])%mod;
                    }
                }
            maxm+=b[x];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while (T--) {
        tot=0;
        cin>>n>>c;
        cin>>C0>>C1>>D0>>D1;
        forn(i,1,n) {
            int x;
            cin>>x>>b[i];
            G[x].push_back(i);
            tot+=b[i];
        }
        tot=min(max({C0,C1,D0,D1}),tot);
        int h1;
        cin>>h1;
        forn(i,1,h1) {
            int x,y;
            cin>>x>>y;
            h[x]=y+1;
        }
        solve_hate();
        solve_no_hate();
        int ans=0;
        tot=0;
        forn(i,1,n) 
            tot+=b[i];
        forn(i,0,C0) 
            forn(j,0,D0) {
                int pre1=tot-C1-i-1>=0?f1[tot-C1-i-1]:0,pre2=tot-D1-j-1>=0?g1[tot-D1-j-1]:0;
                ans=(ans+f[now][i][j]*(f1[C0-i]-pre1+mod)%mod*(g1[D0-j]-pre2+mod)%mod)%mod;
            }
        if (ans==0) cout<<f[now][0][0]<<' '<<f1[C0]<<' '<<g1[D0]<<' '<<tot-C1<<' '<<'\n';
        cout<<ans<<'\n';
        clear();
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 0ms

memory: 5800kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 8316kb

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:

result:

wrong answer 1st lines differ - expected: '5184', found: '2155'

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 8348kb

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
463555763
1 1 785918 79 
0
131405274

result:

wrong answer 3rd lines differ - expected: '85170', found: '463555763'

Test #4:

score: 0

Wrong Answer

time: 0ms

memory: 8304kb

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
1 0 0 -1 
0
1 1 836563581 74 
0
991268888

result:

wrong answer 3rd lines differ - expected: '15230976', found: '1 0 0 -1 '

Test #5:

score: 0

Wrong Answer

time: 22ms

memory: 15900kb

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:

result:

wrong answer 1st lines differ - expected: '335527780', found: '0 0 0 -212 '

Test #6:

score: 0

Wrong Answer

time: 37ms

memory: 42228kb

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
1 0 699327310 -59 
0
1 1 269171742 778 
0
591791292

result:

wrong answer 3rd lines differ - expected: '604706636', found: '1 0 699327310 -59 '

Test #7:

score: 0

Wrong Answer

time: 77ms

memory: 40196kb

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:

wrong answer 1st lines differ - expected: '721598186', found: '856998840'

Test #8:

score: 0

Wrong Answer

time: 68ms

memory: 40208kb

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:

result:

wrong answer 1st lines differ - expected: '139292860', found: '465692426'

Test #9:

score: 0

Wrong Answer

time: 190ms

memory: 124104kb

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
1 0 0 -241 
0
1 1 507275543 1976 
0
143791691

result:

wrong answer 3rd lines differ - expected: '65626616', found: '1 0 0 -241 '

Test #10:

score: 0

Wrong Answer

time: 354ms

memory: 124052kb

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:

wrong answer 3rd lines differ - expected: '890567148', found: '228345956'