QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884385 | #10011. Lottery | bulijiojiodibuliduo | WA | 13ms | 3968kb | C++17 | 1.5kb | 2025-02-06 02:34:59 | 2025-02-06 02:34:59 |
Judging History
This is a historical verdict posted at 2025-02-06 02:34:59.
- [2025-02-06 03:29:21]
- hack成功,自动添加数据
- (/hack/1522)
- [2025-02-06 03:22:12]
- hack成功,自动添加数据
- (/hack/1521)
- [2025-02-06 03:14:39]
- hack成功,自动添加数据
- (/hack/1520)
- [2025-02-06 03:05:58]
- hack成功,自动添加数据
- (/hack/1519)
- [2025-02-06 03:02:43]
- hack成功,自动添加数据
- (/hack/1518)
- [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);
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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: 3968kb
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: 6ms
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: 6ms
memory: 3968kb
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: 5ms
memory: 3968kb
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: 5ms
memory: 3840kb
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: 5ms
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: 6ms
memory: 3968kb
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: 6ms
memory: 3840kb
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: 6ms
memory: 3840kb
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: 7ms
memory: 3968kb
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: 6ms
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: 5ms
memory: 3968kb
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: 7ms
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: 3840kb
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: 5ms
memory: 3968kb
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: 4ms
memory: 3840kb
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: 6ms
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: 3840kb
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: 5ms
memory: 3968kb
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: 6ms
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: 3968kb
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: 3968kb
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: 5ms
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: 3840kb
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: 5ms
memory: 3840kb
input:
1 1000000 1000000 300 1
output:
399999813500 11547
result:
ok 2 number(s): "399999813500 11547"