QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#866333 | #9916. Defeat the Enemies | piggy123 | TL | 2521ms | 95396kb | C++17 | 4.1kb | 2025-01-22 14:33:17 | 2025-01-22 14:33:24 |
Judging History
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
■■■■■ ■■ ■■■ ■■■ ■ ■ ■ ■■■■ ■■■■
■ ■■ ■■ ■ ■■ ■ ■■ ■ ■ ■■ ■ ■■ ■■ ■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■■ ■■ ■■ ■ ■■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■ ■■ ■■
■ ■ ■■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■■ ■ ■■■ ■ ■■■ ■■ ■■ ■■ ■■■
■■■■■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■ ■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■■ ■ ■■ ■■
■ ■■ ■■■■ ■■■■ ■■ ■■ ■■■■■■ ■■■■
*/
Details
Tip: Click on the bar to expand more detailed information
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 ...