QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#866333#9916. Defeat the Enemiespiggy123TL 2521ms95396kbC++174.1kb2025-01-22 14:33:172025-01-22 14:33:24

Judging History

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

  • [2025-01-22 14:33:24]
  • 评测
  • 测评结果：TL
  • 用时：2521ms
  • 内存：95396kb
查看
  • [2025-01-22 14:33:17]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct pl {
	ll a,b;
} p[500005];
ll c[105];
pair<ll,ll> dp[40105][105];
ll gx[105][40105],MX[40105];
const ll mod=998244353;

inline void upd(pair<ll,ll> &a,ll b,ll c) {
	if (a.first>b) {
		a.first=b;
		a.second=c;
	} else if (a.first==b) {
		a.second+=c;
		a.second%=mod;
	}
}

int main() {
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	ll t;
	cin >> t;
	while (t--) {
		ll n,m;
		cin >> n >> m;
		for (ll i=1; i<=n; i++) {
			cin >> p[i].a;
		}
		for (ll i=1; i<=n; i++) {
			cin >> p[i].b;
		}
		ll k;
		cin >> k;
		for (ll i=1; i<=k; i++) {
			cin >> c[i];
		}
		ll mx=0;
		for (ll i=1; i<=n; i++) {
			mx=max(mx,p[i].a+p[i].b);
		}
		for (ll i=0; i<=mx+k*k; i++){
			for (ll j=0; j<=k; j++)
				dp[i][j]= {(ll)1e18,0};
		}
		for (ll i=1;i<=m;i++)MX[i]=0;
		for (ll i=1;i<=n;i++)MX[p[i].b]=max(MX[p[i].b],p[i].a);
		for (ll a=1; a<=k; a++) {
			for (ll i=0; i<=mx+k*k; i++) {
				gx[a][i]=0;
				for (ll j=i+1;j<=min(m,i+a);j++){
					gx[a][i]=max(gx[a][i],MX[j]+i+a-mx);
				}		
				gx[a][i]=min(gx[a][i],k);
			}
		}
		dp[0][0]={0,1};
		for (ll i=0; i<=mx+k*k; i++) {
			for (ll j=0; j<=k; j++) {
				for (ll a=1; a<=k&&i+a<=mx+k*k; a++) {
					// sm>=p[i].a+i+a
					// p[i].b in [i+1,i+a]
					upd(dp[i+a][max(gx[a][i],j)],dp[i][j].first+c[a],dp[i][j].second);
				}
			}
		}
		pair<ll,ll> zw={(ll)1e18,0};
		for (ll i=mx;i<=mx+k*k;i++){
			for (ll j=0;j<=k;j++){
				if (i>=mx+j)
				upd(zw,dp[i][j].first,dp[i][j].second);
			}
		}
		cout<< zw.first<<" "<< zw.second<< "\n";
	}
	return 0;
}

/*
 4
 5 5
 3 5 2 1 2
 3 1 3 2 3
 3
 2 3 4
 3 2
 2 2 2
 2 2 2
 3
 2 3 3
 7 6
 5 3 4 6 6 3 4
 4 6 4 2 3 5 5
 4
 2 4 6 7
 10 100
 38 49 79 66 49 89 21 55 13 23
 67 56 26 39 56 16 84 50 92 82
 11
 6 6 7 8 9 9 9 9 9 9 9
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11876kb

input:

4
5 5
3 5 2 1 2
3 1 3 2 3
3
2 3 4
3 2
2 2 2
2 2 2
3
2 3 3
7 6
5 3 4 6 6 3 4
4 6 4 2 3 5 5
4
2 4 6 7
10 100
38 49 79 66 49 89 21 55 13 23
67 56 26 39 56 16 84 50 92 82
11
6 6 7 8 9 9 9 9 9 9 9

output:

9 1
6 4
18 18
99 44387

result:

ok 8 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 9956kb

input:

1000
5 3
1 1 3 1 2
3 2 1 1 2
1
5
5 3
3 3 2 2 1
1 1 3 1 1
3
3 1 3
5 5
4 3 5 1 4
5 5 2 5 5
2
1 5
5 5
5 5 5 5 4
2 1 2 4 1
2
1 1
5 3
2 1 2 1 1
1 3 2 1 1
1
5
2 1
1 1
1 1
3
2 2 1
5 5
2 3 5 2 2
5 2 4 3 1
2
3 3
5 1
1 1 1 1 1
1 1 1 1 1
3
5 4 4
5 4
1 4 4 4 2
4 3 1 3 3
1
2
1 5
2
2
3
4 2 4
1 5
4
5
1
4
2 5
1 5
1...

output:

20 1
3 1
9 1
5 4
20 1
2 1
15 4
8 4
14 1
4 1
36 1
12 1
27 1
2 1
20 1
4 1
10 1
23 1
10 1
4 1
28 1
4 1
5 1
4 1
6 1
8 1
6 1
16 1
9 6
5 1
30 1
4 1
4 1
2 1
35 1
10 1
2 1
4 1
15 6
4 1
20 1
4 1
6 1
40 1
4 1
18 1
8 1
7 1
6 1
2 1
10 1
3 1
9 1
8 1
4 1
6 4
20 1
8 2
10 1
2 1
2 1
50 1
24 1
6 1
10 16
10 1
6 1
3 1
...

result:

ok 2000 numbers

Test #3:

score: 0
Accepted
time: 449ms
memory: 28412kb

input:

200
50 16
15 15 15 14 15 13 15 15 14 15 16 16 16 12 16 16 16 16 14 13 14 16 13 16 13 16 14 13 16 16 12 14 16 15 13 16 14 16 12 15 14 15 13 14 15 15 15 15 16 13
13 14 16 13 16 16 16 15 13 15 13 16 15 15 16 16 16 16 16 15 16 16 14 12 15 16 16 16 13 12 15 15 16 12 15 14 16 16 16 12 16 16 16 16 15 14 15...

output:

14 6889
68 33856
60 841
388 14400
20 214369
100 1
72 8281
6 256
39 30
4 1
58 1
12 144
4 144
116 169
46 38416
100 1
26 11025
88 36
80 1
10 81
114 100
92 413318192
56 1
50 1296
400 481524050
68 1
32 9
6 1
1100 1
100 103437186
46 1600
80 57
44 576
92 1
26 441
7 320
106 9
68 29241
34 324
29 7878
4 1
4 1...

result:

ok 400 numbers

Test #4:

score: 0
Accepted
time: 96ms
memory: 64728kb

input:

1
500000 10000
3544 1546 5208 6621 759 9303 9198 8910 9046 2355 5960 2034 7059 8504 4449 9573 3020 7106 6973 2021 5158 6148 386 3559 5050 9264 9497 2912 1170 7698 4529 4172 7729 3382 7613 3770 6552 2365 2193 9581 146 7853 5384 4589 3369 3102 9585 3124 1886 8301 8125 3842 4101 5388 3571 10 7190 2464 ...

output:

22388256114 1

result:

ok 2 number(s): "22388256114 1"

Test #5:

score: 0
Accepted
time: 1073ms
memory: 71272kb

input:

5
41415 228
216 219 186 142 203 168 225 177 190 214 171 210 212 220 216 215 209 224 226 207 172 218 190 227 194 221 178 207 220 188 226 227 226 225 197 181 201 223 205 209 183 212 223 182 228 198 222 181 206 148 177 221 226 226 226 196 216 209 207 214 220 156 201 212 224 228 155 212 179 226 215 166 ...

output:

5914951720 225
12050089308 100
45462868776 1
64065203428 1
24263725416 44100

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 512ms
memory: 95396kb

input:

1
500000 10000
9776 9848 9204 9656 9915 9808 9447 9583 9898 9857 9475 9935 9717 9778 9517 9982 9999 9896 9937 9991 9696 9150 9774 9722 9780 9411 9987 9556 9964 9400 9597 9845 9679 9809 9238 9775 9796 9926 9673 9984 9970 9952 9620 9546 9951 9819 9360 9897 9898 9814 9861 9996 9998 9587 9905 9624 9473 ...

output:

1346000 1

result:

ok 2 number(s): "1346000 1"

Test #7:

score: 0
Accepted
time: 2ms
memory: 9836kb

input:

1000
10 3
1 2 3 1 2 2 3 2 1 1
1 3 2 3 3 3 3 1 1 1
2
10 7
4 10
4 8 4 6
5 8 9 6
3
3 4 3
3 2
1 2 1
2 2 2
4
4 8 8 2
10 10
1 2 4 7 1 3 5 9 8 9
2 7 3 1 5 1 10 2 9 6
1
9
3 3
2 3 3
3 3 1
4
7 8 1 5
2 2
2 2
2 2
3
8 7 5
6 9
5 3 3 5 1 9
3 7 1 3 2 3
4
6 7 2 3
3 8
4 1 3
8 3 5
5
6 2 9 4 7
10 7
3 2 2 5 3 1 6 3 2 3
...

output:

28 1
18 1
4 1
153 1
2 1
10 1
8 1
12 10
9 6
24 1
38 35
99 1
22 4
2 1
21 1
12 1
8 1
22 12
20 4
12 1
8 1
2 1
8 1
4 1
6 1
10 2
8 1
2 1
33 3
34 1
26 3
35 1
27 1
5 1
45 1
6 1
16 1
6 1
5 1
8 2
12 1
3 1
20 1
2 4
25 1
57 1
10 1
30 1
24 1
50 36
108 1
80 1
10 1
6 1
64 1
40 1
10 1
7 1
10 1
19 1
12 1
4 1
6 1
4 1...

result:

ok 2000 numbers

Test #8:

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

input:

1000
20 3
1 3 1 2 2 2 1 3 3 3 3 1 1 2 3 2 2 1 3 3
3 2 3 1 1 2 2 3 2 3 3 1 2 2 1 1 3 2 2 2
8
8 5 3 7 5 8 8 3
20 16
11 8 13 11 5 14 12 3 14 7 12 11 3 16 14 1 8 6 5 7
1 14 9 16 10 14 8 8 1 2 16 9 6 8 7 7 1 4 3 5
8
10 7 2 8 1 6 4 9
16 11
5 10 6 8 6 9 8 3 7 2 2 9 2 7 7 11
11 1 4 7 6 3 1 6 11 5 9 7 1 5 7 ...

output:

6 4
7 1
3 2
4 4
2 1
2 4
2 1
9 1
16 1
12 1
6 3
28 1
17 1
2 1
5 1
4 1
30 18
4 1
16 1
40 1
8 1
10 1
17 4
60 1
4 1
6 1
4 1
2 4
22 1
32 1
24 12
4 1
98 105
4 4
2 4
25 1
2 1
6 1
6 18
12 1
54 336
6 1
8 1
35 1
2 4
6 2
8 1
15 1
10 1
2 1
4 1
30 1
22 1
78 1
138 81
63 1
4 3
10 1
6 1
10 4
2 1
12 1
6 1
4 1
28 1
7 ...

result:

ok 2000 numbers

Test #9:

score: 0
Accepted
time: 69ms
memory: 13952kb

input:

1000
30 6
3 4 4 6 6 6 5 6 6 5 4 6 6 6 4 5 5 4 6 4 4 3 6 5 5 5 5 5 6 6
6 6 6 6 6 5 4 6 5 6 6 4 5 6 6 5 4 5 5 6 6 6 3 6 6 4 5 5 6 6
20
3 4 5 8 14 18 24 24 32 35 38 59 60 62 71 79 79 80 80 98
30 2
1 2 1 2 1 1 1 2 1 1 2 2 1 1 1 2 2 2 2 1 1 2 2 2 2 2 2 1 2 2
2 2 1 2 2 2 1 1 1 1 2 2 2 1 1 1 2 2 1 2 1 2 2 ...

output:

20 1
74 1
108 16
16 1
28 1
126 1
156 1
84 1
234 81
94 1
299 1
60 1
286 100
130 16
332 16
14 1
30 1
200 4
80 1
72 1
358 9
110 1
410 64
70 1
74 1
6 1
6 1
92 1
94 25
24 1
42 1
72 1
32 1
420 1
32 1
364 1
60 3
22 1
28 4
188 4
420 1
10 4
44 1
51 6
1570 121
4 1
48 1
80 1
48 1
120 1
396 1
108 1
688 25
178 1...

result:

ok 2000 numbers

Test #10:

score: 0
Accepted
time: 71ms
memory: 13952kb

input:

1000
30 8
4 8 5 7 7 8 5 8 7 3 8 5 6 3 6 3 8 8 6 6 5 8 7 4 6 6 7 5 8 6
7 8 6 7 6 8 8 3 7 8 7 7 8 8 5 8 3 5 8 5 8 8 6 7 8 5 6 7 8 8
9
4 8 23 27 29 51 52 88 96
30 2
2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 1 1 2 2 2 2 2 1 2 1 2 2 2 1 2
2 2 1 2 2 1 2 2 1 1 1 2 2 1 2 1 1 2 2 2 2 2 1 2 2 2 2 2 1 1
9
8 13 29 48 52 69...

output:

64 1156
26 1
264 16
252 1
16 1
96 1
28 1
90 9
94 9
94 9
28 1
16 1
1768 1
290 4
8 1
60 1
80 1
120 1
150 4
1568 1
994 100
24 1
18 1
52 1
40 1
22 1
182 1
84 1
176 225
1162 1
320 9
1121 1
144 1
14 1
196 1
4 1
76 1
264 1
4 1
8 1
19 4895
6 9
110 1
88 4
828 1
18 1
18 1
70 1
250 441
56 1
1711 2716504
2910 1...

result:

ok 2000 numbers

Test #11:

score: 0
Accepted
time: 69ms
memory: 15976kb

input:

1000
9 9
9 8 5 7 5 9 9 6 9
4 5 7 9 7 5 6 5 9
18
7 8 15 17 22 24 34 34 38 48 53 56 73 76 77 86 94 99
7 3
3 1 1 3 1 3 3
2 1 2 3 1 3 1
14
8 9 9 11 13 16 32 43 64 66 83 91 93 96
30 6
3 6 6 6 3 3 5 2 3 5 4 5 4 5 5 6 1 4 3 5 5 6 6 6 6 2 4 4 6 3
2 6 6 3 6 5 4 3 5 6 6 5 2 5 3 4 6 6 5 4 4 2 1 6 3 6 6 5 5 5
1...

output:

76 16
18 1
48 1
2040 1
120 1
75 4
104 1
8 1
1562 1
40 1
8 1
50 1
20 1
448 1
132 1
196 1
246 1
42 1
96 1
58 4
72 4
4 1
32 1
368 1
20 1
24 1
272 1
64 9
26 1
45 1
276 4
1885 1
27 1
210 1
58 36
24 4
336 1
250 1
17 3
816 1
134 1
2 1
126 1
132 1
190 1
24 1
1068 1
18 1
4 1
30 1
3995 1
95 6
106 1
26 1
28 4
...

result:

ok 2000 numbers

Test #12:

score: 0
Accepted
time: 2521ms
memory: 28288kb

input:

1000
9 39
22 25 20 10 28 39 27 19 27
12 39 16 32 39 6 2 31 23
28
1 1 2 2 4 5 6 6 7 8 8 8 9 9 9 10 11 12 13 14 14 14 15 17 18 19 19 20
43 3
2 1 2 2 3 1 1 2 3 2 1 1 1 3 1 1 3 3 3 2 3 1 2 1 2 2 2 3 3 1 1 3 1 2 1 2 2 1 1 1 3 2 3
3 3 3 1 2 2 2 3 3 3 1 3 2 2 3 1 3 2 2 2 1 3 2 3 3 1 2 1 2 1 1 3 3 3 2 1 2 1...

output:

34 104133710
2 4
2 1
31 1576239
13 9
46 10
7 18
6 8
7 1
16 1
34 4
19 10
12 16
35 11
2 1
15 69
4 36
15 5214
11 1
24 6
6 4
2 4
2 4
2 4
7 18
90 1
12 410
5 30
6 9
6 100
31 7
11 121
12 5
10 4
6 36
22 81
2 16
2 1
4 3
8 81
8 21
19 1
30 1
2 1
10 183
2 1
70 1
8 25
17 1
4 1
6 12
17 1
18 1
7 96
2 4
4 16
20 4
4...

result:

ok 2000 numbers

Test #13:

score: 0
Accepted
time: 257ms
memory: 28388kb

input:

100
453 4
2 1 2 1 1 2 3 2 3 4 3 2 3 4 3 3 3 3 2 4 2 4 1 4 3 4 1 2 2 3 4 4 2 1 3 4 2 4 1 4 1 3 2 2 4 4 2 4 1 4 2 1 3 2 1 4 4 4 1 1 3 4 4 4 4 3 3 3 3 4 2 3 1 4 4 4 1 3 1 3 2 3 4 4 3 2 4 3 2 1 4 4 3 2 1 3 1 2 1 4 2 4 1 2 2 3 4 1 4 3 3 2 2 3 4 4 3 4 3 2 1 1 4 4 4 3 2 3 4 1 2 1 2 4 4 4 3 4 4 2 4 2 2 2 3 ...

output:

6 1
150 1
190 1
84 9
150 1
250 760839507
16 249001
50 1
64 37249
68 49
4 4
58 841
1134 1156
48 136900
512 1
972 1
60 49
68 5053504
32 16641
200 1
40 1
44 9
90 1
100 324
68 5198400
64 1
24 1
106 4225
100 1
102 1
1000 1
120 1
12 784
94 400
54 2704
30 199007449
6 49
52 140625
78 3721
14 1521
232 784
68...

result:

ok 200 numbers

Test #14:

score: -100
Time Limit Exceeded

input:

100
1520 54
42 51 47 54 38 52 51 54 48 47 48 42 39 54 51 50 47 54 38 52 51 52 48 51 49 52 41 54 40 54 44 51 48 53 45 50 42 37 41 54 37 53 46 45 52 54 45 51 43 53 53 40 41 42 43 49 49 51 53 41 53 54 54 51 46 38 52 45 53 53 47 54 47 54 51 50 50 54 53 53 47 47 54 54 43 53 45 43 53 54 45 42 44 52 44 53 ...

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-02-01 16:51:27 | 开源项目