QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#208259 | #4233. Reset | ucup-team1209# | AC ✓ | 1841ms | 15064kb | C++20 | 1.1kb | 2023-10-09 12:28:45 | 2023-10-09 12:28:46 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using i128 = __int128;
const int N = 200005;
int n, c;
struct pr { int val; ll cnt; };
int t[N], d[N];
ll st;
std::vector<pr> v;
int check(ll T) {
v.clear();
i128 mx = 0;
for(int i = 1;i <= n;++i) {
int turn = t[i] / d[i];
if(turn >= T) {
v.push_back({d[i], T});
++mx;
} else {
v.push_back({d[i], turn});
if(t[i] % d[i]) {
if (turn == T - 1) ++mx;
v.push_back({t[i] % d[i], 1});
}
}
}
sort(v.begin(), v.end(), [](auto x, auto y) {
return x.val > y.val;
});
i128 ccc = 0;
for (auto vv : v) ccc += vv.cnt;
mx = std::max<i128>(ccc - i128(T-1) * c, mx);
i128 cnt = (i128) T * c;
ll sum = 0;
for(auto x : v) {
ll sub = std::min<i128>(cnt, x.cnt);
sum += x.val * sub;
cnt -= sub;
}
return st - sum <= c - mx;
}
int main() {
cin >> n >> c;
for(int i = 1;i <= n;++i) {
cin >> t[i] >> d[i];
st += t[i];
}
ll l = 0, r = 1e18 + 1;
for(;l + 1 < r;) {
ll mid = (l + r) >> 1;
if(check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << r - 1 << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
3 5 17 5 5 2 15 4
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 1345 1344 1 10 10
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 1000000000 1000000000 1
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
3 2345 333 1 444 2 555 3
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 500 1000 2
output:
250
result:
ok single line: '250'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 499 1000 2
output:
250
result:
ok single line: '250'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
3 2345 3333 5 4444 6 5555 6
output:
646
result:
ok single line: '646'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
8 6 40 10 40 10 40 10 40 10 40 10 20 5 4 3 5 3
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
8 6 40 10 40 10 40 10 40 10 40 10 20 5 7 3 5 3
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
5 4 29 8 30 7 2000 1000 2000 1000 2000 1000
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
27 19 21 5 14 5 14 5 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000
output:
4
result:
ok single line: '4'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
24 21 25 8 13 7 13 7 13 7 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000 3000 1000
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
4 2 10 10 10 10 10 10 9 2
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 189ms
memory: 6116kb
input:
110000 60000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 100000 222200000 10000...
output:
99999
result:
ok single line: '99999'
Test #15:
score: 0
Accepted
time: 307ms
memory: 9444kb
input:
200000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 10000...
output:
199999999999999
result:
ok single line: '199999999999999'
Test #16:
score: 0
Accepted
time: 1036ms
memory: 14088kb
input:
200000 7 966486041 28 936158040 29 991239679 47 988279269 31 905558493 68 998009820 40 901181342 66 925252807 10 995161072 3 947576761 21 980670741 66 931584704 3 944714227 42 992178536 6 905079737 39 982672468 87 963094272 21 919244645 48 935633595 3 903091417 4 923453539 72 916293313 82 981382022 ...
output:
1405907290168
result:
ok single line: '1405907290168'
Test #17:
score: 0
Accepted
time: 1055ms
memory: 14508kb
input:
200000 313 955333176 37 901868728 50 941539297 29 986447408 44 991503201 16 960466782 13 941404760 26 906572773 27 983407691 42 968036098 75 978785905 2 930572618 67 968054047 14 972769762 39 903513789 23 966791626 84 992080584 65 976672158 15 912399245 35 961103319 25 920979048 64 959902065 72 9685...
output:
31397952846
result:
ok single line: '31397952846'
Test #18:
score: 0
Accepted
time: 749ms
memory: 14284kb
input:
200000 10 23 21 17 5 5 5 9 2 29 24 14 7 24 23 30 8 10 10 29 27 1 1 3 2 18 7 17 12 26 3 13 6 7 4 28 20 5 1 16 3 24 5 22 4 27 11 11 5 1 1 12 4 1 1 12 3 30 5 26 24 11 9 21 19 1 1 4 4 8 1 29 22 10 8 3 1 24 12 7 7 25 18 11 10 20 19 20 19 20 10 27 26 2 2 12 7 24 18 19 15 19 10 11 4 12 4 2 1 27 9 3 3 19 5 ...
output:
70162
result:
ok single line: '70162'
Test #19:
score: 0
Accepted
time: 571ms
memory: 14000kb
input:
200000 10 4 1 8 4 11 4 15 2 3 3 7 3 14 3 27 4 17 4 4 4 11 5 19 1 29 4 9 5 2 1 30 5 5 1 27 5 20 2 6 5 3 3 30 3 18 2 13 5 16 3 21 3 8 3 17 4 10 5 16 3 8 2 16 3 8 4 4 4 2 2 8 3 30 4 15 1 21 3 19 3 12 5 3 1 23 2 9 3 15 5 4 2 11 3 15 4 5 3 1 1 28 2 12 3 15 3 5 1 6 5 3 1 4 3 18 2 26 4 29 5 7 3 19 2 13 1 1...
output:
147252
result:
ok single line: '147252'
Test #20:
score: 0
Accepted
time: 720ms
memory: 14728kb
input:
200000 100 18 11 12 3 10 6 28 26 17 2 2 2 6 5 15 12 18 7 26 8 29 18 6 1 20 10 14 4 3 2 3 2 4 2 7 6 7 4 9 2 21 19 11 8 23 19 3 2 10 10 17 12 24 21 12 10 30 22 29 17 12 5 5 4 9 3 20 12 7 6 17 5 5 5 30 4 8 2 29 1 30 25 16 13 25 23 2 1 24 23 10 3 10 10 7 4 24 13 1 1 26 26 3 2 10 3 17 6 14 7 28 18 3 1 17...
output:
7021
result:
ok single line: '7021'
Test #21:
score: 0
Accepted
time: 559ms
memory: 15064kb
input:
200000 100 3 2 6 3 18 4 14 5 4 1 1 1 25 1 22 1 15 1 2 2 16 2 3 2 11 2 29 4 21 3 13 2 4 1 7 3 13 5 5 2 13 3 19 2 8 3 3 2 22 3 16 1 28 1 26 4 19 3 7 5 22 1 10 3 19 1 5 3 2 2 18 1 5 1 16 2 12 3 20 1 12 5 25 5 20 3 23 2 17 4 30 3 24 1 24 4 16 1 18 1 21 3 9 4 7 5 28 4 1 1 15 2 24 3 1 1 14 1 26 1 27 3 28 ...
output:
14737
result:
ok single line: '14737'
Test #22:
score: 0
Accepted
time: 741ms
memory: 13488kb
input:
200000 1000 13 1 29 7 22 15 17 12 30 25 20 7 28 12 13 13 8 5 22 7 9 6 20 15 2 2 23 16 13 2 21 1 27 9 1 1 13 5 18 9 28 2 28 8 12 12 10 6 2 2 19 16 4 4 14 14 10 5 7 1 16 16 26 14 5 2 20 12 5 5 3 3 10 7 22 21 7 6 4 3 21 17 22 12 7 5 6 6 17 6 16 6 30 6 22 4 29 16 4 3 29 3 26 17 21 15 21 20 14 13 27 24 1...
output:
698
result:
ok single line: '698'
Test #23:
score: 0
Accepted
time: 565ms
memory: 13104kb
input:
200000 1000 27 5 2 2 29 4 9 2 16 4 15 3 29 3 1 1 21 2 2 1 21 3 17 4 12 2 26 2 1 1 8 5 29 2 5 3 4 3 9 4 5 5 30 2 11 4 20 5 25 1 22 2 21 1 1 1 5 2 13 4 26 1 5 2 7 3 21 2 27 5 17 3 24 2 25 1 26 4 15 2 5 1 15 5 26 2 6 5 27 4 3 1 19 5 27 4 24 5 3 1 17 4 25 5 1 1 20 2 22 4 12 5 1 1 6 3 25 1 15 1 22 2 10 2...
output:
1474
result:
ok single line: '1474'
Test #24:
score: 0
Accepted
time: 725ms
memory: 13340kb
input:
200000 998642531 14 6 13 3 2 1 9 6 15 12 10 1 11 9 21 13 23 8 29 8 28 26 1 1 27 5 17 3 14 14 22 11 27 19 5 2 9 3 2 1 11 4 9 3 8 5 28 12 12 7 29 12 19 5 29 16 24 3 20 10 2 2 6 3 9 5 6 4 3 2 18 3 16 3 27 5 14 14 29 23 21 17 22 13 1 1 13 2 21 7 13 1 21 16 11 1 18 8 28 17 14 6 24 8 30 15 29 4 4 2 13 12 ...
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 1419ms
memory: 13332kb
input:
200000 10 3684 3080 3014 1370 3226 2869 4168 3400 3744 45 4280 670 4898 1215 4699 1387 3103 2201 4357 1267 4602 1765 3290 1180 3556 3370 4198 3434 3743 3324 4592 4451 3328 2499 4848 2244 3879 2853 3676 2630 4758 3917 3057 1758 3045 279 4784 3965 4530 4183 4435 1460 3239 978 4034 269 4046 3652 3626 2...
output:
188403
result:
ok single line: '188403'
Test #26:
score: 0
Accepted
time: 1431ms
memory: 13340kb
input:
200000 100 3019 973 3932 1011 3415 2658 3428 2971 3566 1447 4647 2270 4083 135 3876 3207 3505 2148 3979 3087 3314 1757 3116 1 3785 3297 3220 2212 3585 3462 3583 3195 4654 3563 3951 704 3535 1229 3941 1769 3804 3085 4218 1581 3241 2950 3445 2551 4753 25 4583 1820 4466 2945 3572 2641 3500 503 4403 180...
output:
18881
result:
ok single line: '18881'
Test #27:
score: 0
Accepted
time: 932ms
memory: 13908kb
input:
200000 100 3294 37 3313 44 3463 9 3349 46 4444 11 3206 16 3046 16 3592 32 4838 50 4871 40 3105 8 3646 41 4136 30 4592 3 4921 2 3218 24 4452 30 3038 5 3604 22 4593 7 4475 20 3372 16 3014 19 4959 42 4863 45 3607 31 4304 48 3682 25 3651 16 3586 10 3478 17 4524 25 4611 41 4411 47 3228 14 3786 35 4114 50...
output:
721052
result:
ok single line: '721052'
Test #28:
score: 0
Accepted
time: 1446ms
memory: 13408kb
input:
200000 1000 3760 3035 4707 305 3581 1906 4963 787 4825 3243 3176 750 4163 45 3109 1115 3249 864 4367 3432 3858 1478 3291 689 3421 2877 3092 719 4735 3136 4462 781 3092 2834 3907 1499 4234 4135 3777 1128 4546 1996 3986 1907 4808 4629 4907 4167 3770 947 3589 173 3438 1497 4594 4389 3067 1223 4668 4087...
output:
4698
result:
ok single line: '4698'
Test #29:
score: 0
Accepted
time: 1447ms
memory: 14752kb
input:
200000 10000 4431 3806 4004 3485 4665 4535 4410 1029 4584 2925 3215 1749 4461 951 4201 2434 4443 2307 3258 2988 4546 3074 4069 2626 4667 4586 3063 1858 3278 1795 4560 2041 4515 260 4444 2831 3153 385 3009 750 4856 2376 4353 254 3732 976 3182 1612 4532 3688 4914 1417 4069 2048 3685 1402 4836 2445 396...
output:
3945
result:
ok single line: '3945'
Test #30:
score: 0
Accepted
time: 929ms
memory: 13048kb
input:
200000 10000 3194 48 3378 17 3107 14 4004 6 3831 9 3375 8 3905 37 3754 29 3266 29 4651 40 3595 32 4108 40 3628 6 3380 34 3178 20 4693 9 3009 29 4761 24 3780 42 3042 20 3883 18 3781 1 3842 38 3928 7 4488 3 3356 50 4688 21 4491 39 4975 18 3956 40 4507 2 3495 27 4731 5 4749 38 3919 10 3622 10 3765 17 4...
output:
7243
result:
ok single line: '7243'
Test #31:
score: 0
Accepted
time: 1395ms
memory: 13888kb
input:
200000 936459299 4490 3508 4411 4089 4574 4346 4986 1762 3949 1395 3817 3130 3275 1494 4886 1288 4544 4241 3712 1588 3010 1570 4783 4359 3234 1613 4026 2009 4232 2940 3686 3313 4500 2835 4180 751 4052 679 4901 990 3927 344 3814 2690 4155 1765 3002 846 4694 326 4218 3048 4532 518 4716 1771 3687 3293 ...
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 623ms
memory: 13296kb
input:
200000 984365240 948008790 4 917968673 5 916371433 1 920084719 5 961214689 4 978284904 2 951405682 2 988955890 3 956391151 2 935114279 4 946380955 5 908225059 3 930643776 2 948070216 1 936295824 2 979801389 4 954164107 2 957063005 3 929215803 1 998330260 4 987902706 3 926594054 4 975993529 3 9004574...
output:
997761885
result:
ok single line: '997761885'
Test #33:
score: 0
Accepted
time: 970ms
memory: 14460kb
input:
200000 835926446 965657505 38 900646315 40 933747285 30 934258718 47 944421292 4 990162734 21 988554019 13 982450425 3 913838799 21 937995251 4 951324685 14 991422256 13 942720235 43 976347806 20 973533405 43 944101225 2 981383733 9 951471928 15 940063532 17 979849241 38 997117700 25 950218304 36 96...
output:
993574358
result:
ok single line: '993574358'
Test #34:
score: 0
Accepted
time: 1841ms
memory: 13400kb
input:
200000 899676145 934015774 456786697 999258553 73656031 974402807 462725421 950994566 333655222 986255970 331370722 950395776 691220359 945459838 438858652 928227924 752687628 979345613 370802068 977136573 797428342 903898193 763003062 902299799 179280636 950647950 829486508 918240243 757385104 9823...
output:
234778
result:
ok single line: '234778'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
3 2 3 1 3 3 2 2
output:
2
result:
ok single line: '2'