QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884385#10011. LotterybulijiojiodibuliduoWA 13ms3968kbC++171.5kb2025-02-06 02:34:592025-02-06 03:14:53

Judging History

This is the latest submission verdict.

  • [2025-02-06 03:29:21]
  • hack成功,自动添加数据
  • (/hack/1522)
  • [2025-02-06 03:22:12]
  • hack成功,自动添加数据
  • (/hack/1521)
  • [2025-02-06 03:14:53]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: WA
  • Time: 13ms
  • Memory: 3968kb
  • [2025-02-06 03:14:39]
  • hack成功,自动添加数据
  • (/hack/1520)
  • [2025-02-06 03:06:20]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: 100
  • Time: 13ms
  • Memory: 3968kb
  • [2025-02-06 03:05:58]
  • hack成功,自动添加数据
  • (/hack/1519)
  • [2025-02-06 03:02:51]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: 100
  • Time: 12ms
  • Memory: 3968kb
  • [2025-02-06 03:02:43]
  • hack成功,自动添加数据
  • (/hack/1518)
  • [2025-02-06 02:34:59]
  • Judged
  • Verdict: 100
  • Time: 13ms
  • Memory: 3968kb
  • [2025-02-06 02:34:59]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int M=10000;

int n,b[333];
int f[M+10];
ll s,r;
struct frac {
	ll a,b;
};
bool operator < (frac a, frac b) {
	return (__int128)a.a*b.b<(__int128)b.a*a.b;
}
int main() {
	scanf("%d%lld%lld",&n,&s,&r);
	s*=r;
	rep(i,0,n) {
		int a,c;
		scanf("%d%d",&a,&c);
		b[a]=max(b[a],c);
	}
	int op=-1;
	rep(i,1,301) {
		if (op==-1||b[i]*op>b[op]*i) op=i;
	}
	f[0]=0;
	rep(i,0,M) rep(j,1,301) if (i>=j) {
		f[i]=max(f[i],f[i-j]+b[j]);
	}
	frac ans{1ll<<60,1};
	rep(i,0,M) {
		//(i + a[op] * t) + s / (f[i] + b[op] * t)
		int tt=int(max(sqrt(1.*s/op/b[op]) - 1.*f[i]/b[op],0.0));
		for (ll t=max(tt-10,0);t<=tt+10;t++) if (f[i]+b[op]*t>0) {
			frac p{s,f[i]+b[op]*t};
			p.a=p.a+(i+op*t)*(f[i]+b[op]*t);
			if (p<ans) ans=p;
		}
	}
	ll d=gcd(ans.a,ans.b);
	printf("%lld %lld\n",ans.a/d,ans.b/d);
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 3840kb

input:

3 11 3
1 3
2 7
5 13

output:

63 10

result:

ok 2 number(s): "63 10"

Test #2:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

8 608515 751563
113 451
9 4537
19 3343
79 855
260 4457
59 1650
142 3631
239 788

output:

914765325642 15185339

result:

ok 2 number(s): "914765325642 15185339"

Test #3:

score: 0
Accepted
time: 7ms
memory: 3840kb

input:

17 679894 524637
207 3634
275 1104
227 3130
226 1339
151 2999
121 2642
199 4470
112 4688
34 19
272 3032
84 2180
114 659
33 124
52 2086
212 546
199 497
198 311

output:

356598985567 1931456

result:

ok 2 number(s): "356598985567 1931456"

Test #4:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

20 405440 588704
40 1481
54 810
150 3034
160 684
201 516
78 3790
293 1138
60 4899
99 2881
272 4500
257 4419
234 3179
136 4965
286 2826
113 1880
234 362
19 3747
117 4676
213 2847
269 2556

output:

477363025033 6860757

result:

ok 2 number(s): "477363025033 6860757"

Test #5:

score: 0
Accepted
time: 7ms
memory: 3840kb

input:

30 4555 13594
96 2403
47 4203
185 1292
178 4525
270 2327
83 297
102 4540
112 4855
284 4174
137 591
285 431
140 3107
154 433
105 3472
139 1862
298 3961
174 3440
56 716
76 4202
61 4170
223 4661
244 867
6 3372
181 2008
204 3705
106 48
266 2909
215 1675
149 1484
74 4426

output:

12312247 18546

result:

ok 2 number(s): "12312247 18546"

Test #6:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

300 161804 259017
72 1783
266 3081
108 313
207 3609
104 1245
166 4606
95 1424
297 2169
151 3212
43 2757
143 3990
264 3562
77 2008
104 4307
209 2432
36 1184
257 3943
117 3749
139 332
223 1001
114 3847
140 2784
137 3334
126 4370
255 1923
92 18
45 3731
138 1815
59 3600
100 2190
76 3593
199 422
249 3557...

output:

13967804171 1152849

result:

ok 2 number(s): "13967804171 1152849"

Test #7:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

5000 662829 786670
295 679
42 65
242 1599
102 4840
212 1201
257 603
63 1385
62 3509
224 603
64 2390
89 4938
254 3091
169 2900
59 1387
143 3628
244 4339
263 4775
273 1915
207 3847
152 4311
99 4611
157 504
51 4925
299 2696
296 2234
45 2553
146 3934
142 1047
172 1678
26 2721
266 2467
254 1876
243 1814
...

output:

34762782969 1651954

result:

ok 2 number(s): "34762782969 1651954"

Test #8:

score: 0
Accepted
time: 13ms
memory: 3840kb

input:

100000 141764 497259
13 4586
257 415
233 4107
109 8
4 4815
68 3480
134 609
133 2967
178 2172
232 841
298 1676
115 2196
277 4091
64 2715
128 1077
289 966
166 2836
73 3984
248 4404
31 2432
266 744
98 344
184 1588
208 4537
70 1768
81 2165
232 2675
155 3772
126 4678
60 3632
190 2437
241 960
81 546
138 2...

output:

2237911095 297677

result:

ok 2 number(s): "2237911095 297677"

Test #9:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

17 10737 10481
290 4747
48 478
61 782
260 2789
128 1211
103 1530
70 1142
185 49
132 1049
123 608
26 29
201 646
262 4270
248 359
188 2696
276 4407
36 29

output:

529649 101

result:

ok 2 number(s): "529649 101"

Test #10:

score: 0
Accepted
time: 5ms
memory: 3712kb

input:

17 9380 873235
13 125
57 593
163 1516
135 1252
107 1242
128 1538
255 3556
39 182
259 1854
182 2298
39 494
257 792
149 538
23 335
121 536
280 4146
48 349

output:

585075485 12438

result:

ok 2 number(s): "585075485 12438"

Test #11:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

17 966641 9074
96 1206
139 907
44 100
93 707
120 1441
87 567
116 866
261 4044
138 2097
68 826
236 2087
193 869
194 619
196 1914
120 334
50 14
113 1424

output:

673529363 14154

result:

ok 2 number(s): "673529363 14154"

Test #12:

score: 0
Accepted
time: 5ms
memory: 3968kb

input:

17 933110 954688
249 2282
68 462
213 1168
133 2173
248 1240
222 1686
44 716
194 2641
155 2166
57 344
126 1810
202 479
279 4061
282 2445
271 4486
188 3065
165 1718

output:

111351279456 240001

result:

ok 2 number(s): "111351279456 240001"

Test #13:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

20 9572 9562
17 149
179 2710
112 320
217 478
118 191
59 627
142 1615
185 1196
201 920
243 3699
233 2852
31 367
163 2545
178 527
113 715
91 403
225 966
127 322
216 1148
151 1695

output:

184865339 38175

result:

ok 2 number(s): "184865339 38175"

Test #14:

score: 0
Accepted
time: 5ms
memory: 3712kb

input:

20 10372 934957
89 207
204 1984
115 52
134 95
258 2925
120 1252
290 2729
202 938
218 2857
171 420
49 811
114 1329
213 18
242 1952
204 2582
294 4132
93 71
38 462
68 17
64 70

output:

9697560304 200317

result:

ok 2 number(s): "9697560304 200317"

Test #15:

score: 0
Accepted
time: 5ms
memory: 3840kb

input:

20 960625 10209
172 1470
98 1579
193 931
84 416
271 3142
80 83
38 413
116 1196
285 2975
56 867
247 221
246 1761
62 382
116 1021
286 2930
65 796
263 2483
199 2706
266 2278
168 743

output:

6544585531 132636

result:

ok 2 number(s): "6544585531 132636"

Test #16:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

20 898754 886528
290 3880
286 2959
68 251
297 4301
159 1401
284 3973
112 1848
233 2590
276 3595
285 1755
166 482
229 3055
144 1142
118 1032
95 1249
71 1041
98 416
219 101
183 292
96 512

output:

99594569216 226611

result:

ok 2 number(s): "99594569216 226611"

Test #17:

score: 0
Accepted
time: 7ms
memory: 3968kb

input:

50 9738 9828
139 756
218 3104
5 23
120 91
147 686
206 3346
104 1229
78 873
189 744
252 1270
173 1693
210 399
120 854
188 223
269 3395
89 339
119 1230
208 1760
105 563
64 244
158 2046
245 1411
194 48
141 627
34 508
191 2735
112 147
43 576
157 1205
123 1455
9 64
292 1369
146 1050
159 197
2 5
285 666
2...

output:

1836377 383

result:

ok 2 number(s): "1836377 383"

Test #18:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

50 10314 967998
163 969
135 165
198 1932
91 607
225 1649
75 940
128 170
230 2124
193 602
123 1895
102 730
184 890
194 2451
64 699
89 1170
107 1523
88 1179
93 766
250 182
106 1266
101 596
233 1669
298 2915
12 184
117 1455
298 3659
197 1850
49 138
138 1694
120 1970
178 481
215 1755
271 1210
241 2427
2...

output:

5003950443 101455

result:

ok 2 number(s): "5003950443 101455"

Test #19:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

50 850782 10871
246 3349
29 73
276 3710
145 2104
31 37
42 696
280 1101
152 1062
64 96
16 249
300 1520
17 189
239 3694
134 672
179 1423
186 122
61 834
254 3270
45 47
211 1751
71 414
237 3527
260 2381
129 1115
1 13
185 2356
98 346
162 941
209 1197
125 442
169 423
55 375
15 160
183 1860
169 2013
36 248...

output:

3080267155 65192

result:

ok 2 number(s): "3080267155 65192"

Test #20:

score: 0
Accepted
time: 5ms
memory: 3712kb

input:

50 963353 920567
210 651
207 3016
277 165
298 4318
112 38
188 586
195 1541
72 864
50 151
107 1111
209 2865
1 16
157 2416
106 462
290 2446
106 739
243 2183
201 1382
149 668
60 779
287 2494
14 19
159 2351
44 522
272 88
129 2090
114 1703
214 1603
26 340
183 519
283 2157
225 284
222 3130
18 193
123 427
...

output:

1774008568711 3791260

result:

ok 2 number(s): "1774008568711 3791260"

Test #21:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

100 10458 9781
61 21
247 1933
130 1274
159 1841
272 2392
244 474
294 3389
238 32
173 2629
30 478
34 357
209 2592
273 1545
59 11
287 2554
217 2346
162 575
16 32
128 1950
295 743
107 1379
84 2
68 314
236 3063
103 392
187 2695
209 1440
40 217
278 3417
7 6
232 1634
42 551
90 735
124 1697
297 3390
78 154...

output:

14574381 2933

result:

ok 2 number(s): "14574381 2933"

Test #22:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

100 9143 862886
21 280
11 86
113 127
49 87
252 40
203 2932
22 241
84 337
111 319
80 666
71 150
17 149
214 2670
185 536
209 2341
194 2782
111 214
78 1239
289 3444
75 836
43 214
279 2314
92 1228
45 638
154 1653
126 407
68 423
17 73
58 27
280 3877
208 43
285 2564
211 445
195 228
55 826
206 2154
155 407...

output:

15818204923 361305

result:

ok 2 number(s): "15818204923 361305"

Test #23:

score: 0
Accepted
time: 6ms
memory: 3968kb

input:

100 811506 10684
300 4367
204 644
191 840
299 2428
57 461
170 2702
182 2693
298 3052
290 316
273 28
268 882
262 1195
63 249
255 3588
103 784
272 1794
280 1839
239 694
76 159
75 1037
116 1779
180 1473
250 3320
162 1415
122 1957
13 171
268 3849
130 2061
36 467
89 608
295 3757
118 732
47 296
128 1417
1...

output:

2168710667 47477

result:

ok 2 number(s): "2168710667 47477"

Test #24:

score: 0
Accepted
time: 5ms
memory: 3840kb

input:

100 929574 952696
54 773
127 1854
206 1810
249 912
9 144
25 254
106 1398
149 653
126 183
23 281
203 2219
140 8
298 4445
6 44
22 38
118 1010
119 1336
91 1433
124 145
125 373
214 2328
282 3687
147 1750
281 3216
23 366
134 1146
42 601
155 1759
44 478
78 942
152 1789
117 677
73 142
84 284
144 978
138 20...

output:

858118269 1856

result:

ok 2 number(s): "858118269 1856"

Test #25:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

300 10527 10146
172 230
30 25
211 2090
297 3867
213 2145
184 1119
187 2265
256 391
191 953
69 342
166 575
253 4043
55 675
281 4453
247 1337
196 105
251 1609
278 4243
105 1202
118 89
39 390
212 1967
147 879
124 1013
181 1866
185 94
228 267
215 1145
37 38
281 3183
221 355
244 2116
220 482
174 232
209 ...

output:

11898019 2350

result:

ok 2 number(s): "11898019 2350"

Test #26:

score: 0
Accepted
time: 6ms
memory: 3968kb

input:

300 9592 827989
4 21
229 2707
15 52
249 1829
248 1542
209 257
21 62
108 1296
158 2355
29 333
160 1916
300 668
224 2780
72 1196
176 558
294 3132
41 473
264 3230
71 785
184 1076
157 808
24 145
30 92
61 402
297 4624
17 144
82 289
3 5
10 160
151 1759
139 1521
160 1105
158 565
252 931
7 46
175 2336
253 3...

output:

7963646978 182361

result:

ok 2 number(s): "7963646978 182361"

Test #27:

score: 0
Accepted
time: 5ms
memory: 3840kb

input:

300 820417 10249
86 133
18 65
101 35
199 1159
158 1600
169 2014
69 554
218 540
37 430
19 38
161 2459
237 2800
73 259
141 493
71 964
261 3144
6 50
118 345
158 2143
288 2825
238 947
225 558
292 3005
178 2285
273 1252
196 2498
283 3967
116 676
185 1405
260 4261
234 939
96 568
106 600
193 1820
35 415
16...

output:

16836953833 374600

result:

ok 2 number(s): "16836953833 374600"

Test #28:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

300 928166 848682
119 937
10 36
176 1566
183 1249
221 3392
14 29
265 3695
4 8
58 739
241 824
244 2564
81 240
167 2321
14 3
160 537
44 316
252 2506
196 1735
84 1208
105 414
239 540
82 114
291 4693
254 4212
169 570
54 301
69 271
215 298
67 483
129 1939
224 2240
289 965
201 2449
145 236
122 136
62 3
22...

output:

262581076602 603155

result:

ok 2 number(s): "262581076602 603155"

Test #29:

score: 0
Accepted
time: 7ms
memory: 3840kb

input:

5000 10603 10872
117 819
121 1657
130 1775
200 755
181 2009
61 987
260 1629
81 449
229 2409
255 535
162 2313
208 629
185 2728
292 1299
253 1755
51 587
227 462
10 11
294 1072
31 26
252 3262
280 3010
291 4365
281 41
281 2067
1 13
237 2140
37 447
123 136
149 718
223 2474
61 430
3 38
293 2394
37 553
177...

output:

115322583 21925

result:

ok 2 number(s): "115322583 21925"

Test #30:

score: 0
Accepted
time: 5ms
memory: 3840kb

input:

5000 10723 904065
252 2767
233 493
299 4648
63 304
275 2786
231 2317
238 3155
129 326
237 986
218 2883
135 1660
20 240
120 419
283 203
159 1050
138 1288
201 1677
258 2120
152 1342
226 3005
144 1545
238 840
253 402
52 481
182 2544
142 1546
272 429
57 466
230 2687
300 3293
91 52
79 1107
107 872
9 66
1...

output:

3877623429 80390

result:

ok 2 number(s): "3877623429 80390"

Test #31:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

5000 936170 9374
139 68
127 1164
77 891
116 377
80 1104
191 2577
294 1383
239 2777
221 171
215 1025
229 19
152 1817
165 1288
45 740
54 394
217 2234
174 474
112 655
238 1438
30 496
21 172
138 475
215 765
177 404
262 1185
29 330
181 295
170 697
104 145
108 1201
185 485
219 1402
54 532
250 3193
257 397...

output:

1755173773 38245

result:

ok 2 number(s): "1755173773 38245"

Test #32:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

5000 895288 980105
250 646
166 1016
277 4345
144 1522
73 691
106 986
102 351
152 1498
279 1365
133 283
223 3658
289 1853
30 156
250 1144
18 197
159 933
254 142
60 72
103 1494
96 677
250 986
194 2696
27 250
257 1186
189 1954
135 369
88 77
89 376
121 546
86 1322
81 48
100 1219
230 3272
42 24
9 81
101 ...

output:

12535004956 27315

result:

ok 2 number(s): "12535004956 27315"

Test #33:

score: 0
Accepted
time: 7ms
memory: 3840kb

input:

5 1000000 1000000
273 1
256 1
276 2
266 1
254 1

output:

1000004075444 42563

result:

ok 2 number(s): "1000004075444 42563"

Test #34:

score: 0
Accepted
time: 5ms
memory: 3840kb

input:

17 1000000 1000000
253 1
272 2
269 1
261 1
272 2
276 2
292 4
286 2
253 1
280 1
267 1
284 3
272 2
296 3
277 2
261 1
255 1

output:

24999754960 1463

result:

ok 2 number(s): "24999754960 1463"

Test #35:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

20 1000000 1000000
254 1
285 1
282 3
250 1
259 1
265 1
250 1
258 1
250 1
257 1
286 2
279 2
269 1
292 2
287 3
294 4
287 1
293 4
290 2
298 3

output:

49999466130 2921

result:

ok 2 number(s): "49999466130 2921"

Test #36:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

50 1000000 1000000
262 1
275 1
268 1
261 1
280 2
296 2
257 1
296 1
275 2
286 2
275 1
250 1
280 1
276 2
260 1
259 1
273 1
269 1
279 2
277 1
283 1
255 1
280 3
300 2
279 2
287 1
281 1
264 1
252 1
283 3
255 1
254 1
282 1
255 1
294 3
262 1
278 1
292 3
277 2
277 2
292 3
251 1
279 2
267 1
282 1
260 1
281 1...

output:

1999983887560 103509

result:

ok 2 number(s): "1999983887560 103509"

Test #37:

score: 0
Accepted
time: 5ms
memory: 3840kb

input:

1 1 1
1 5000

output:

5001 5000

result:

ok 2 number(s): "5001 5000"

Test #38:

score: 0
Accepted
time: 6ms
memory: 3840kb

input:

1 1000000 1000000
300 1

output:

399999813500 11547

result:

ok 2 number(s): "399999813500 11547"

Extra Test:

score: -3
Extra Test Failed : Wrong Answer on 3
time: 6ms
memory: 3840kb

input:

2 33072 33072
299 298
300 299

output:

83812584 1265

result:

wrong answer 1st numbers differ - expected: '365263821', found: '83812584'