QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#647238	#8354. T2	songziyan	47	1662ms	87340kb	C++14	1.2kb	2024-10-17 12:55:55	2024-10-17 12:55:56

Judging History

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

[2024-10-17 12:55:56]
评测

测评结果：47
用时：1662ms
内存：87340kb

查看

[2024-10-17 12:55:55]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
char buf[1<<22],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?0:*p1++)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch))f=(ch=='-')?-1:1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
const int N=2e6+5;
int n,K,q,B,op[5005],x[5005],ans[5005],f[N],g[N],p[N],v[N],t[N],vis[N];
void add1(int i){for(int j=K;j>=t[i];j--)f[j]=max(f[j],f[j-t[i]]+v[i]);}
void add2(int i){for(int j=K/B;j>=v[i];j--)g[j]=min(g[j],g[j-v[i]]+t[i]);}
void trans(int i){if(p[i]<=B)add1(i);else add2(i);}
signed main(){
    n=read();q=read();K=read();B=sqrt(n+q);
    for(int i=1;i<=n;i++)p[i]=read(),v[i]=read(),t[i]=p[i]*v[i];
    for(int i=1;i<=q;i++){
        op[i]=read(),x[i]=read();
        if(op[i]==1)vis[x[i]]=1;
    }
    memset(g,0x3f,sizeof(g));g[0]=0;
    for(int i=1;i<=n;i++)if(!vis[i])trans(i);
    for(int i=q;i>=1;i--)
        if(op[i]==1)trans(x[i]);
        else{int &res=ans[i];for(int j=x[i]/B;j>=0;j--)if(x[i]>=g[j])res=max(res,f[x[i]-g[j]]+j);}
    for(int i=1;i<=q;i++)if(op[i]==2)printf("%lld\n",ans[i]);
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11

Accepted

Test #1:

score: 11

Accepted

time: 0ms

memory: 28540kb

input:

3205 5000 5000
1 1
2 1
3 1
7 1
8 1
9 1
10 1
11 1
12 2
13 1
14 2
16 1
17 2
20 3
22 1
24 1
26 2
27 1
30 1
32 2
33 1
34 1
41 1
44 2
49 2
51 1
54 2
58 2
61 2
65 2
66 1
68 2
70 1
71 2
72 2
74 8
75 3
76 5
77 1
78 7
79 5
80 5
81 1
82 2
84 1
86 6
87 6
88 3
89 9
90 5
91 1
92 2
93 3
95 7
96 2
97 2
98 8
99 8
1...

output:

result:

ok 2487 lines

Test #2:

score: 11

Accepted

time: 5ms

memory: 28488kb

input:

162 5000 5000
836 4
837 5
838 5
839 5
840 4
841 4
842 4
843 4
844 4
845 4
846 5
847 4
848 4
849 5
850 4
851 5
852 5
853 4
854 5
855 4
856 5
857 4
858 4
859 4
860 5
861 5
862 4
863 4
864 4
865 5
866 5
867 4
868 5
869 4
870 4
871 5
872 4
873 4
874 5
875 4
876 4
877 5
878 5
879 4
880 4
881 5
882 5
883 ...

output:

result:

ok 4838 lines

Test #3:

score: 11

Accepted

time: 0ms

memory: 28584kb

input:

3182 5000 5000
1 2597
2 404
3 409
4 220
5 604
6 248
7 48
8 145
9 97
10 356
11 111
12 158
13 192
14 309
15 168
16 251
17 234
18 68
19 223
20 111
21 235
22 152
23 188
24 48
25 75
26 9
27 34
28 153
29 58
30 18
31 153
32 76
33 150
34 52
35 121
36 37
37 7
38 79
39 96
40 101
41 8
42 66
43 61
44 77
45 83
4...

output:

result:

ok 1818 lines

Test #4:

score: 11

Accepted

time: 4ms

memory: 28676kb

input:

3205 5000 5000
1 1
3 1
6 2
7 1
9 1
12 1
15 1
16 1
18 1
19 1
30 1
37 2
39 1
40 1
43 1
47 1
50 1
52 1
54 1
59 1
63 1
65 1
66 1
70 1
71 52
72 42
73 55
74 37
75 42
76 38
77 36
78 22
79 56
80 12
81 29
82 10
83 53
84 40
85 42
86 39
87 54
88 6
89 2
90 36
91 29
92 6
93 4
94 23
95 20
96 43
97 13
98 1
99 1
10...

output:

result:

ok 4030 lines

Test #5:

score: 11

Accepted

time: 2ms

memory: 26544kb

input:

3240 5000 5000
1 4544
2 2194
3 616
4 99
5 68
6 558
7 36
8 322
9 394
10 113
11 314
12 396
13 221
14 349
15 49
16 219
17 42
18 239
19 178
20 146
21 48
22 96
23 205
24 162
25 14
26 188
27 58
28 71
29 65
30 16
31 111
32 51
33 119
34 63
35 32
36 75
37 100
38 90
39 65
40 44
41 7
42 82
43 62
44 26
45 84
46...

output:

result:

ok 2448 lines

Test #6:

score: 11

Accepted

time: 0ms

memory: 26552kb

input:

3130 5000 5000
1 3
2 1
4 1
5 1
6 1
8 1
9 3
10 2
11 2
13 1
14 2
15 2
17 1
19 1
23 1
24 1
25 1
27 2
30 1
33 2
34 1
35 1
36 1
37 2
38 1
39 3
40 1
41 1
43 2
45 1
46 1
48 1
49 2
50 1
51 1
52 1
53 3
54 2
58 1
60 1
62 1
63 1
64 1
65 1
66 1
68 2
69 2
71 4
72 7
74 3
75 6
77 3
78 9
79 6
80 3
81 7
82 8
83 6
84...

output:

result:

ok 1870 lines

Test #7:

score: 11

Accepted

time: 0ms

memory: 26480kb

input:

3220 5000 5000
1 1716
2 2046
3 1005
4 308
5 629
6 117
7 344
8 562
9 27
10 244
11 177
12 141
13 330
14 87
15 306
16 219
17 211
18 145
19 254
20 58
21 215
22 37
23 135
24 194
25 38
26 12
27 175
28 97
29 39
30 89
31 72
32 64
33 7
34 62
35 30
36 130
37 132
38 12
39 21
40 26
41 68
42 110
43 21
44 108
45 ...

output:

result:

ok 3964 lines

Test #8:

score: 11

Accepted

time: 3ms

memory: 30756kb

input:

3157 5000 5000
2 1
4 1
5 1
8 2
10 1
16 1
18 1
22 1
24 1
25 1
26 2
29 2
34 1
36 1
40 1
42 2
43 1
45 2
46 1
47 1
49 3
51 1
55 1
57 1
67 3
68 1
70 1
71 12
72 18
73 15
74 49
75 15
76 12
77 49
78 9
79 5
80 46
81 38
82 4
83 46
84 58
85 26
86 14
87 13
88 39
89 5
90 51
91 24
92 44
93 51
94 19
95 10
96 16
97...

output:

result:

ok 2523 lines

Test #9:

score: 11

Accepted

time: 0ms

memory: 30532kb

input:

3233 5000 5000
1 4147
2 1080
3 1621
4 237
5 939
6 694
7 374
8 42
9 501
10 222
12 195
13 208
14 75
15 298
16 141
17 213
18 232
19 196
20 65
21 91
22 4
23 48
24 200
25 53
26 139
27 80
28 109
29 19
30 132
31 123
32 43
33 16
34 129
35 138
36 85
37 112
38 44
39 44
40 42
41 103
42 76
43 43
44 19
45 65
46 ...

output:

result:

ok 1767 lines

Test #10:

score: 11

Accepted

time: 0ms

memory: 28576kb

input:

411 5000 5000
1253 3
1254 3
1255 3
1256 3
1257 3
1258 3
1259 3
1260 3
1261 3
1262 3
1263 3
1264 3
1265 3
1266 3
1267 3
1268 3
1269 3
1270 3
1271 3
1272 3
1273 3
1274 3
1275 3
1276 3
1277 3
1278 3
1279 3
1280 3
1281 3
1282 3
1283 3
1284 3
1285 3
1286 3
1287 3
1288 3
1289 3
1290 3
1291 3
1292 3
1293 3...

output:

result:

ok 4589 lines

Subtask #2:

score: 0

Time Limit Exceeded

Test #11:

score: 0

Time Limit Exceeded

input:

1277351 1 2000000
2 2
5 1
7 3
8 4
10 1
12 1
15 2
16 1
18 1
22 1
25 1
28 3
29 1
32 1
35 1
36 1
38 2
40 1
41 2
42 1
43 2
44 2
45 1
48 1
49 1
50 2
54 2
55 2
56 1
58 2
59 2
60 2
62 1
66 1
68 3
69 1
70 3
72 2
76 1
78 1
79 2
81 2
82 3
84 2
85 1
86 2
89 1
90 2
91 2
92 1
93 1
96 3
98 3
99 2
100 3
101 1
102 ...

output:

result:

Subtask #3:

score: 15

Accepted

Test #21:

score: 15

Accepted

time: 160ms

memory: 42292kb

input:

5000 5000 2000000
1 1
2 1
3 1
4 1
6 1
7 1
8 1
9 1
10 1
11 1
14 1
15 3
17 2
18 2
21 1
22 1
24 1
25 3
27 1
28 2
29 1
30 1
31 1
32 1
33 1
34 1
35 1
37 1
38 1
39 1
40 2
41 2
43 1
45 1
47 1
49 1
50 1
51 1
54 1
55 1
56 1
61 1
62 2
64 1
65 1
67 2
68 2
70 2
72 2
74 1
76 3
79 2
82 4
83 2
84 1
88 1
91 1
92 1
...

output:

result:

ok 2447 lines

Test #22:

score: 15

Accepted

time: 131ms

memory: 42960kb

input:

5000 5000 2000000
1 813802
2 134681
3 83044
4 315718
5 197248
6 119339
7 261285
8 156156
9 196051
10 173937
11 48028
12 116232
13 6597
14 105636
15 21987
16 108656
17 21158
18 30668
19 61562
20 79298
21 47690
22 23541
23 19543
24 45753
25 59750
26 24095
27 4249
28 69164
29 19751
30 8053
31 55434
32 ...

output:

result:

ok 1017 lines

Test #23:

score: 15

Accepted

time: 106ms

memory: 43500kb

input:

5000 5000 2000000
4 1
16 1
41 1
60 1
86 1
93 1
125 1
126 1
184 1
249 1
260 1
308 1
311 1
322 1
424 1
427 1
451 1
477 1
523 1
629 1
660 1
680 1
694 1
724 1
731 1
741 1
742 1
743 1
744 1
768 1
798 1
822 1
872 1
874 1
897 1
904 1
950 1
971 1
973 1
982 1
1013 1
1024 1
1047 1
1063 1
1080 1
1121 1
1129 1
...

output:

result:

ok 4022 lines

Test #24:

score: 15

Accepted

time: 170ms

memory: 41780kb

input:

5000 5000 2000000
1 1627103
2 716626
3 665364
4 497570
5 189147
6 82325
7 14868
8 137172
9 169535
10 141421
11 159956
12 63184
13 26342
14 6512
15 18048
16 101458
17 27905
18 12716
19 8580
20 12169
21 12097
22 55619
23 79732
24 18682
25 32267
26 4738
27 32772
28 29008
29 59773
30 19663
31 613
32 579...

output:

result:

ok 2513 lines

Test #25:

score: 15

Accepted

time: 123ms

memory: 41712kb

input:

5000 5000 2000000
3 1
5 1
6 1
7 1
8 1
11 2
14 1
15 1
16 1
22 1
25 1
27 2
28 1
31 1
32 1
33 1
34 2
35 1
36 1
38 1
42 1
43 2
45 1
46 1
50 1
51 1
52 1
53 1
55 1
64 1
65 1
68 1
70 1
71 1
72 1
73 1
76 1
77 1
78 1
85 1
89 1
91 1
92 1
93 1
94 2
96 1
97 1
109 1
110 1
111 2
120 1
126 2
129 1
132 2
134 1
140 ...

output:

result:

ok 988 lines

Test #26:

score: 15

Accepted

time: 206ms

memory: 44696kb

input:

5000 5000 2000000
1 364044
2 300803
3 218421
4 365847
5 63539
6 324669
7 31959
8 232865
9 32717
10 27341
11 29651
12 135000
13 27768
14 117739
15 77947
16 121183
17 50492
18 57533
19 25423
20 33988
21 67414
22 62686
23 85739
24 42313
25 78019
26 47515
27 19440
28 11992
29 29580
30 24818
31 24986
32 ...

output:

result:

ok 4009 lines

Test #27:

score: 15

Accepted

time: 141ms

memory: 42228kb

input:

5000 5000 2000000
4 2
6 1
7 1
9 1
11 2
12 2
14 1
16 2
17 1
18 1
19 1
20 1
23 1
25 3
26 2
27 2
28 1
29 2
30 2
33 2
35 2
36 1
38 1
39 1
41 1
43 1
46 1
47 1
48 1
50 2
54 1
56 1
59 1
60 1
64 1
65 1
66 1
68 1
69 1
70 1
73 2
74 3
75 1
76 1
77 1
80 2
82 1
83 2
84 1
86 1
90 1
92 2
93 2
97 1
98 1
99 1
101 1
...

output:

result:

ok 2475 lines

Test #28:

score: 15

Accepted

time: 135ms

memory: 42220kb

input:

5000 5000 2000000
1 12616
2 968067
3 471331
4 498123
5 174683
6 288045
7 123021
8 247009
9 20861
10 5184
11 167706
12 33538
13 107153
14 4583
15 81246
16 98517
17 42633
18 55345
19 80376
20 94003
21 73198
22 17908
23 36380
24 41210
25 44169
26 63612
27 53280
28 41724
29 57409
30 12451
31 387
32 2001...

output:

result:

ok 978 lines

Test #29:

score: 15

Accepted

time: 93ms

memory: 28624kb

input:

5000 5000 2000000
500003 3
530259 2
661666 3
661667 3
661668 3
661669 3
661670 3
661671 3
661672 3
661673 3
661674 3
661675 3
661676 3
661677 3
661678 3
661679 3
661680 3
661681 3
661682 3
661683 3
661684 3
661685 3
661686 3
661687 3
661688 3
661689 3
661690 3
661691 3
661692 3
661693 3
661694 3
661...

output:

result:

ok 4036 lines

Test #30:

score: 15

Accepted

time: 79ms

memory: 28508kb

input:

5000 5000 2000000
333336 4
333337 5
356720 3
395001 5
395002 5
395003 4
395004 4
395005 5
395006 5
395007 4
395008 5
395009 5
395010 4
395011 5
395012 5
395013 5
395014 5
395015 4
395016 5
395017 5
395018 4
395019 4
395020 5
395021 4
395022 4
395023 5
395024 5
395025 5
395026 4
395027 5
395028 5
395...

output:

result:

ok 2480 lines

Subtask #4:

score: 21

Accepted

Test #31:

score: 21

Accepted

time: 118ms

memory: 39184kb

input:

191299 5000 300000
1 1
5 1
6 2
7 1
8 1
10 1
11 2
12 2
17 1
18 1
19 1
20 1
21 1
22 2
25 1
28 1
29 2
30 1
31 2
34 1
36 1
37 1
38 1
40 1
42 1
43 1
44 1
45 1
47 2
48 1
51 1
53 3
54 2
56 2
58 2
59 2
61 2
63 4
64 2
67 1
68 2
69 2
70 1
72 1
76 1
77 1
78 1
80 2
83 1
84 1
87 1
88 1
89 1
91 2
93 1
95 1
96 1
9...

output:

result:

ok 2476 lines

Test #32:

score: 21

Accepted

time: 126ms

memory: 40912kb

input:

191816 5000 300000
1 74901
2 103360
3 89547
4 67750
5 40186
6 28389
7 24182
8 26076
9 5630
10 26706
11 12730
12 17632
13 7414
14 15422
15 8901
16 10990
17 1835
18 9986
19 10576
20 7349
21 9585
22 730
23 11619
24 955
25 9845
26 10221
27 4553
28 6352
29 543
30 6193
31 8335
32 8880
33 7372
34 2859
35 6...

output:

result:

ok 976 lines

Test #33:

score: 21

Accepted

time: 88ms

memory: 38056kb

input:

193270 5000 300000
22 1
29 1
33 1
40 1
43 1
62 1
63 1
64 1
78 1
80 1
94 1
105 1
106 1
108 1
110 2
120 1
128 1
149 1
203 1
207 1
212 1
234 1
255 2
263 1
266 1
286 1
298 1
300 1
302 1
304 1
313 1
314 2
317 1
327 1
353 1
380 1
384 2
403 1
408 1
426 1
428 1
434 1
442 1
472 1
473 1
476 1
477 1
479 1
490 ...

output:

result:

ok 4004 lines

Test #34:

score: 21

Accepted

time: 118ms

memory: 40236kb

input:

193095 5000 300000
1 94614
2 123167
3 21362
4 23872
5 16365
6 35594
7 38193
8 7725
9 22330
10 19540
11 5255
12 13478
13 5510
14 6237
15 13251
16 14905
17 1701
18 6700
19 8176
20 10001
21 7572
22 8916
23 10170
24 8570
25 10033
26 7465
27 7099
28 6107
29 8603
30 3776
31 4112
32 4161
33 8181
34 7604
35...

output:

result:

ok 2541 lines

Test #35:

score: 21

Accepted

time: 107ms

memory: 40800kb

input:

191758 5000 300000
1 1
2 1
10 1
11 1
14 1
15 1
19 1
23 1
26 3
27 1
31 2
33 1
35 1
38 1
43 1
48 1
49 1
59 1
60 1
62 1
63 1
70 3
73 2
74 1
85 1
91 1
92 1
94 1
97 1
107 1
110 1
114 2
119 1
122 1
124 2
129 1
131 1
137 1
138 1
140 1
145 2
148 1
151 1
153 2
155 1
156 1
160 1
164 1
166 1
167 5
170 1
172 1
...

output:

result:

ok 953 lines

Test #36:

score: 21

Accepted

time: 118ms

memory: 38336kb

input:

192547 5000 300000
1 259492
2 36730
3 19495
4 50645
5 14448
6 4834
7 27102
8 4737
9 31914
10 10057
11 10294
12 1471
13 9103
14 18481
15 18059
16 4633
17 3934
18 10299
19 4682
20 7800
21 1509
22 11812
23 852
24 2660
25 9322
26 3312
27 4782
28 7141
29 3014
30 7195
31 3522
32 3530
33 3921
34 6837
35 74...

output:

result:

ok 4052 lines

Test #37:

score: 21

Accepted

time: 115ms

memory: 40232kb

input:

193235 5000 300000
2 1
5 1
10 1
12 1
14 1
17 1
19 1
20 1
24 2
26 2
28 2
32 1
36 1
37 1
40 2
42 1
51 2
53 1
54 1
57 1
60 3
64 1
65 2
68 2
69 1
73 1
74 1
76 1
78 1
82 1
83 1
84 1
86 2
90 1
91 2
92 2
93 2
95 1
97 1
102 2
104 1
105 1
107 1
111 1
112 1
113 1
117 1
119 2
120 1
121 2
122 2
123 1
126 1
129 ...

output:

result:

ok 2481 lines

Test #38:

score: 21

Accepted

time: 125ms

memory: 38660kb

input:

193127 5000 300000
1 118752
2 84001
3 9258
4 69673
5 35782
6 5615
7 14451
8 15585
9 19755
10 10853
11 3647
12 19328
13 8157
14 159
15 8439
16 4582
17 9117
18 14953
19 12846
20 320
21 1617
22 13279
23 10378
24 11925
25 9680
26 3611
27 7787
28 1585
29 5620
30 2865
31 935
32 8592
33 370
34 1099
35 162
...

output:

result:

ok 1055 lines

Test #39:

score: 21

Accepted

time: 26ms

memory: 28936kb

input:

24995 5000 300000
75003 3
75004 3
75005 3
75006 3
75007 3
75008 3
75009 3
75010 3
75011 3
75012 3
75013 3
75014 3
75015 3
75016 3
75017 3
75018 3
75019 3
75020 3
75021 3
75022 3
75023 3
75024 3
75025 3
75026 3
75027 3
75028 3
75029 3
75030 3
75031 3
75032 3
75033 3
75034 3
75035 3
75036 3
75037 3
75...

output:

result:

ok 4043 lines

Test #40:

score: 21

Accepted

time: 19ms

memory: 28700kb

input:

9995 5000 300000
50003 4
50004 4
50005 5
50006 5
50007 4
50008 4
50009 5
50010 4
50011 5
50012 5
50013 5
50014 5
50015 5
50016 4
50017 4
50018 4
50019 4
50020 4
50021 5
50022 4
50023 4
50024 4
50025 4
50026 5
50027 4
50028 5
50029 5
50030 4
50031 5
50032 5
50033 5
50034 5
50035 4
50036 5
50037 5
500...

output:

result:

ok 2499 lines

Subtask #5:

score: 0

Time Limit Exceeded

Test #41:

score: 40

Accepted

time: 1662ms

memory: 87340kb

input:

1278949 5000 2000000
4 1
9 1
12 1
13 1
15 2
20 1
21 2
26 1
36 1
39 2
43 1
46 2
59 1
64 1
66 1
71 1
73 1
75 1
78 2
83 1
87 1
89 1
92 1
97 1
103 1
104 1
108 1
111 1
113 1
114 1
117 2
118 1
130 1
137 1
140 1
151 1
152 1
155 1
158 2
163 1
164 1
165 1
168 1
172 1
173 1
183 1
185 1
186 1
192 1
208 1
210 2...

output:

result:

ok 2474 lines

Test #42:

score: 0

Time Limit Exceeded

input:

1278613 5000 2000000
1 1222462
2 456727
3 334990
4 330207
5 222769
6 52941
7 247811
8 131230
9 73420
10 187657
11 45883
12 121991
13 31509
14 94454
15 21739
16 118643
17 67978
18 22774
19 24405
20 4442
21 74797
22 10974
23 8219
24 11261
25 4112
26 39242
27 62294
28 71371
29 10931
30 53060
31 54203
3...

output: