QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#648593	#8354. T2	kgqy	0	196ms	59920kb	C++14	1.3kb	2024-10-17 19:37:50	2024-10-17 19:37:50

Judging History

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

[2024-10-17 19:37:50]
评测

测评结果：0
用时：196ms
内存：59920kb

查看

[2024-10-17 19:37:50]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int w=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) w=w*10+ch-'0',ch=getchar();
	return w;
}
const int B=70;
int n,m,k;
int f[2000005],g[1005];
int dis[2000005],val[2000005];
int sop[2000005],sx[2000005];
int vis[2000005],ans[2000005];
main(){
	n=read(),m=read(),k=read();
	memset(g,0x3f,sizeof(g));g[0]=0;
	for(int i=1;i<=n;i++) dis[i]=read(),val[i]=read();
	for(int i=1;i<=m;i++){
		sop[i]=read(),sx[i]=read();
		if(sop[i]==1) vis[sx[i]]=1;
	}
	for(int i=1;i<=n&&dis[i]<B;i++){
		if(vis[i]) continue;
		for(int j=k;j>=dis[i]*val[i];j--) f[j]=max(f[j],f[j-dis[i]*val[i]]+val[i]);
	}
	for(int i=n;i&&dis[i]>=B;i--){
		if(vis[i]) continue;
		for(int j=k/dis[i];j>=val[i];j--) g[j]=min(g[j],g[j-val[i]]+dis[i]*val[i]);
	}
	for(int i=m;i;i--){
		if(sop[i]==2){
			int lim=sx[i];
			for(int j=0;j<=k/B&&g[j]<=lim;j++){
				ans[i]=max(ans[i],j+f[lim-g[j]]);
			}
		}else{
			int p=sx[i];
			if(dis[p]<B){
				for(int j=k;j>=dis[p]*val[p];j--) f[j]=max(f[j],f[j-dis[p]*val[p]]+val[p]);
			}else{
				for(int j=k/B;j>=val[i];j--) g[j]=min(g[j],g[j-val[p]]+dis[p]*val[p]);
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(sop[i]==2) printf("%lld\n",ans[i]);
	}
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 11

Accepted

time: 0ms

memory: 16108kb

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: 0ms

memory: 18180kb

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: 0

Wrong Answer

time: 3ms

memory: 16228kb

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:

wrong answer 6th lines differ - expected: '60', found: '59'

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 0

Wrong Answer

time: 84ms

memory: 49288kb

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:

wrong answer 1st lines differ - expected: '1771', found: '28628'

Subtask #3:

score: 0

Wrong Answer

Test #21:

score: 0

Wrong Answer

time: 196ms

memory: 30532kb

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:

wrong answer 1st lines differ - expected: '1778', found: '28630'

Subtask #4:

score: 0

Wrong Answer

Test #31:

score: 21

Accepted

time: 27ms

memory: 22792kb

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: 0

Wrong Answer

time: 26ms

memory: 20972kb

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:

wrong answer 1st lines differ - expected: '75673', found: '79956'

Subtask #5:

score: 0

Wrong Answer

Test #41:

score: 0

Wrong Answer

time: 177ms

memory: 59920kb

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:

wrong answer 3rd lines differ - expected: '1207', found: '28590'