QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90885 | #366. Long Distance Coach | He_Ren | 100 ✓ | 162ms | 19132kb | C++23 | 2.1kb | 2023-03-26 02:16:58 | 2023-03-26 02:17:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 LL;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 5;
const ll linf = 0x3f3f3f3f3f3f3f3f;
struct Vector {
LL x, y;
LL get(LL k) const {
return y - k * x;
}
};
Vector operator - (const Vector &p, const Vector &q) {
return Vector{p.x - q.x, p.y - q.y};
}
LL cross(const Vector &p, const Vector &q) {
return p.x * q.y - p.y * q.x;
}
ll s[MAXN];
array<ll, 2> p[MAXN];
ll val[MAXN], sum[MAXN], dp[MAXN];
int main(void) {
int n, m;
ll X, W, T;
scanf("%lld%d%d%lld%lld", &X, &n, &m, &W, &T);
for (int i = 1; i <= n; ++i)
scanf("%lld", &s[i]);
for (int i = 1; i <= m; ++i)
scanf("%lld%lld", &p[i][0], &p[i][1]);
p[0] = {0, 0};
s[++n] = X;
sort(p + 1, p + m + 1);
memset(val, 0x3f, sizeof(val));
for (int i = 1; i <= n; ++i) {
int pos = lower_bound(p + 1, p + m + 1, array<ll, 2> {s[i] % T, 0}) - p - 1;
if (pos >= 1)
val[pos] = min(val[pos], s[i] / T * W);
}
for (int i = 1; i <= m; ++i)
sum[i] = sum[i - 1] + p[i][1] - ((X - p[i][0]) / T + 1) * W;
static Vector h[MAXN];
int hd = 1, tl = 0;
auto push = [&](Vector cur) {
while (hd + 1 <= tl && cross(cur - h[tl], cur - h[tl - 1]) >= 0)
--tl;
h[++tl] = cur;
};
auto query = [&](LL k) {
int l = hd, r = tl;
while (l < r) {
int mid = (l + r) >> 1;
if (h[mid + 1].get(k) <= h[mid].get(k))
l = mid + 1;
else
r = mid;
}
return h[l].get(k);
};
dp[0] = 0;
push(Vector{0, (LL)dp[0] - sum[0]});
for (int i = 1; i <= m; ++i) {
dp[i] = dp[i - 1];
if (val[i] < linf) {
dp[i] = min((LL)dp[i], query(val[i]) + sum[i] + (LL)i * val[i]);
}
push(Vector{i, (LL)dp[i] - sum[i]});
}
ll ans = dp[m];
for (int i = 0; i <= m; ++i)
ans += ((X - p[i][0]) / T + 1) * W;
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 16
Accepted
Test #1:
score: 16
Accepted
time: 1ms
memory: 5160kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 0
Accepted
time: 3ms
memory: 5304kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: 0
Accepted
time: 3ms
memory: 5100kb
input:
5 1 1 15 4 3 2 13
output:
43
result:
ok single line: '43'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5152kb
input:
5 1 1 15 4 3 2 19
output:
45
result:
ok single line: '45'
Test #5:
score: 0
Accepted
time: 3ms
memory: 5300kb
input:
142 4 7 10 13 67 44 86 141 3 1000000000 6 1000000000 9 1000000000 1 60 4 81 7 48 10 14
output:
878
result:
ok single line: '878'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5092kb
input:
142 3 8 10 13 68 46 37 4 1000000000 8 1000000000 1 61 2 59 5 79 6 79 9 20 10 155
output:
982
result:
ok single line: '982'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5304kb
input:
150 8 8 10 18 5 88 75 87 83 14 109 112 17 30 7 70 2 24 10 25 12 34 9 92 8 30 13 18
output:
463
result:
ok single line: '463'
Test #8:
score: 0
Accepted
time: 3ms
memory: 5040kb
input:
10000000000 8 8 6 18 9547257284 4226673527 9454195771 9513946487 7287482436 6692534804 3951479147 8774939403 12 415893810 4 735304001 13 184845346 14 354080601 15 455062532 16 886416267 3 985580216 1 97417991
output:
18443869092
result:
ok single line: '18443869092'
Test #9:
score: 0
Accepted
time: 2ms
memory: 5304kb
input:
200 4 8 5 14 136 180 37 58 13 39 8 100 3 33 11 32 6 62 5 1 7 98 1 32
output:
601
result:
ok single line: '601'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5088kb
input:
200 8 8 5 18 73 40 168 152 10 12 122 178 3 46 5 30 7 18 9 40 11 24 13 12 15 17 17 9
output:
370
result:
ok single line: '370'
Test #11:
score: 0
Accepted
time: 3ms
memory: 5156kb
input:
99999999999 7 7 3 16 75171012465 68638795379 63875989701 83563043959 64144786889 89597405323 74981605181 2 105022615 4 341401908 6 209850215 8 507409549 10 849182839 12 760157370 14 257217651
output:
116398917650
result:
ok single line: '116398917650'
Test #12:
score: 0
Accepted
time: 3ms
memory: 5100kb
input:
150 8 8 10 18 146 49 17 101 117 134 131 33 1 1 3 1 7 5215 12 2283658 4 69 14 23058601 16 170888234 10 148221
output:
751
result:
ok single line: '751'
Test #13:
score: 0
Accepted
time: 0ms
memory: 5164kb
input:
8001 7 8 6 17 3613 4410 5581 2885 1918 934 6395 10 131687242 13 284628020 2 541922 15 554928957 4 4115226 6 17341529 1 16935 8 52922149
output:
25422
result:
ok single line: '25422'
Test #14:
score: 0
Accepted
time: 3ms
memory: 5312kb
input:
250 8 8 10 18 238 189 86 221 120 173 53 205 6 300728 13 24836451 8 2800753 15 946925513 2 293 10 17341529 1 251803956 3 16935
output:
1260
result:
ok single line: '1260'
Test #15:
score: 0
Accepted
time: 2ms
memory: 5148kb
input:
1234567 8 8 1000000 18 2 22 42 62 82 102 122 142 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1
output:
137203000007
result:
ok single line: '137203000007'
Test #16:
score: 0
Accepted
time: 0ms
memory: 5088kb
input:
1234567 8 8 999 18 449660 490828 187404 376334 697798 1177644 1056704 312928 3 996683357 5 928740029 7 950657139 9 904761397 11 923725553 13 962648669 15 971692610 17 965766352
output:
616666716
result:
ok single line: '616666716'
Test #17:
score: 0
Accepted
time: 2ms
memory: 5168kb
input:
200 8 8 12 18 131 170 55 60 47 28 158 192 13 40 16 87 17 69 4 55 7 99 9 975663280 15 17 3 912112332
output:
1159
result:
ok single line: '1159'
Test #18:
score: 0
Accepted
time: 3ms
memory: 5152kb
input:
600 8 8 63 18 340 333 326 328 331 339 332 337 5 17 3 12 11 26 14 18 12 943485371 17 25 10 954990891 1 48
output:
15089
result:
ok single line: '15089'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5152kb
input:
300 8 8 11 18 135 256 73 167 222 223 206 46 3 22 11 9 15 54 17 47 16 10 13 34 14 54 2 55
output:
1373
result:
ok single line: '1373'
Test #20:
score: 0
Accepted
time: 3ms
memory: 5308kb
input:
300 8 8 11 18 109 113 205 26 208 290 168 189 11 6 13 43 15 21 3 60 17 11 14 69 16 50 4 61
output:
1392
result:
ok single line: '1392'
Test #21:
score: 0
Accepted
time: 4ms
memory: 5156kb
input:
300 8 8 11 18 205 201 265 59 261 268 251 186 14 38 2 17 10 60 1 76 11 6 8 11 15 44 4 42
output:
1285
result:
ok single line: '1285'
Test #22:
score: 0
Accepted
time: 4ms
memory: 5160kb
input:
1000000000000 2 8 1 12 993108218019 991995612814 9 240664344 11 304345424 2 53636225 6 980780804 1 630139807 7 493422072 5 645833104 8 715127198
output:
748927437875
result:
ok single line: '748927437875'
Subtask #2:
score: 30
Accepted
Dependency #1:
100%
Accepted
Test #23:
score: 30
Accepted
time: 3ms
memory: 5092kb
input:
40404 100 100 100 202 11311 6858 1342 33586 9137 32534 4418 17596 219 36087 27700 32608 9038 37603 9907 4425 20347 34228 16795 19358 39055 17874 20748 8085 25371 33809 20385 22674 1777 2761 26337 23244 33018 3026 27376 32600 6038 22197 17477 388 23977 10456 27452 6343 25010 765 9535 8908 4134 4284 3...
output:
1710307
result:
ok single line: '1710307'
Test #24:
score: 0
Accepted
time: 3ms
memory: 5040kb
input:
1000000000000 100 100 2 202 328357813456 903330009313 164185997981 231561194553 124550158519 296392508550 475599519385 900825035172 189235656551 408784569411 483033980726 336217024948 278904951489 995121215037 943411844411 156124098161 755105443489 749582869428 62956166430 689364357815 264627842323 ...
output:
92553156821
result:
ok single line: '92553156821'
Test #25:
score: 0
Accepted
time: 3ms
memory: 5044kb
input:
40809 100 100 95 202 21615 6871 28286 5260 9302 25464 17992 2440 35772 13554 17596 6488 12146 39216 13766 32 13366 238 22662 4484 9536 16406 36204 23884 13786 40048 32576 9954 18238 21270 39856 19456 31780 3502 20876 10374 5124 6540 9168 4322 19070 40080 34628 39680 3726 25140 11810 12822 27570 2474...
output:
1724152
result:
ok single line: '1724152'
Test #26:
score: 0
Accepted
time: 3ms
memory: 5100kb
input:
60199 100 100 15 202 4041 4448 55152 25460 34552 13748 19810 33144 51528 17594 58602 54362 24872 23056 47096 33160 21446 27104 16400 16604 28322 1862 27114 29944 59842 45906 32172 32578 27126 52580 32584 35818 6530 28954 31380 48552 14618 53404 8966 7756 35230 45938 46344 9784 11806 20696 57260 3019...
output:
268962
result:
ok single line: '268962'
Test #27:
score: 0
Accepted
time: 3ms
memory: 5308kb
input:
65536 100 100 10 202 15719 65259 44533 65473 8864 7251 65451 60046 65487 39693 11486 56020 8259 25793 13704 62263 63674 10881 60447 14710 34657 32240 40701 65456 21157 48360 5034 26599 41306 22972 52796 6445 33850 24383 29016 49367 65452 65258 38684 56422 54809 23577 53600 35660 65469 33248 50376 40...
output:
295768
result:
ok single line: '295768'
Test #28:
score: 0
Accepted
time: 3ms
memory: 5088kb
input:
99999 100 100 245 202 17539 14516 42540 37504 57654 34480 30242 9476 3427 47782 66525 81847 21369 72772 25603 76001 50602 23184 99793 93947 16128 45765 78018 53422 70760 32260 15523 20160 79027 97982 80840 29233 98990 63503 84066 77009 89107 28628 52818 90920 2218 68744 13106 41734 54832 1211 56443 ...
output:
12088526
result:
ok single line: '12088526'
Test #29:
score: 0
Accepted
time: 4ms
memory: 5100kb
input:
1000000000000 100 100 559132 202 323529417495 794117660130 676470599579 941176486281 725490208431 225490199989 274509808640 29411765389 450980399582 49019608647 352941182685 470588243446 862745112643 480392164773 656862755916 303921574034 441176478259 529411773829 823529425524 774509816672 970588251...
output:
8222537296663272
result:
ok single line: '8222537296663272'
Test #30:
score: 0
Accepted
time: 3ms
memory: 5076kb
input:
1000000000000 100 100 559132 202 794117660331 882352955701 823529425321 78431373842 941176486280 705882364758 156862747881 225490200194 656862755906 686274521297 98039217302 323529417296 588235303998 392156869609 549019617078 166666669612 205882356532 500000008634 627450990917 970588251472 490196086...
output:
8222540297522718
result:
ok single line: '8222540297522718'
Test #31:
score: 0
Accepted
time: 3ms
memory: 5172kb
input:
77777777 100 100 777777 202 1 205 409 613 817 1021 1225 1429 1633 1837 2041 2245 2449 2653 2857 3061 3265 3469 3673 3877 4081 4285 4489 4693 4897 5101 5305 5509 5713 5917 6121 6325 6529 6733 6937 7141 7345 7549 7753 7957 8161 8365 8569 8773 8977 9181 9385 9589 9793 9997 10202 10406 10610 10814 11018...
output:
602798175078
result:
ok single line: '602798175078'
Test #32:
score: 0
Accepted
time: 1ms
memory: 5096kb
input:
9999999 100 100 9999 202 8114745 1921225 982735 1324319 3187569 1402901 1284329 3785495 5348977 3374631 9315453 6890849 1966899 797523 8523823 4473119 3111439 2470293 5533827 673911 7342135 3874403 6690083 9136305 542419 4483643 1852191 1136507 607269 9020975 9532845 2715549 8555573 8420033 5752221 ...
output:
49995000000
result:
ok single line: '49995000000'
Test #33:
score: 0
Accepted
time: 4ms
memory: 5308kb
input:
9999999 100 100 19600 202 2760937 1304519 4383001 2385425 8328873 4344627 2938911 1288977 1293827 8385645 3523911 9778843 5759651 5117091 9807735 8204059 4132145 1993977 8679371 3532413 7505957 389903 2825015 6727253 8409309 5595249 9138129 3767961 3038743 9128237 5867959 5630611 6070569 5414677 119...
output:
97640895969
result:
ok single line: '97640895969'
Test #34:
score: 0
Accepted
time: 0ms
memory: 5044kb
input:
100000 100 100 31 202 66008 20233 27880 96660 60745 51880 81893 82036 9567 29386 56196 60137 35604 73348 84764 96466 72291 54591 83860 37818 69653 60055 56255 51912 90778 64277 78238 96672 28164 63932 45195 31470 64496 93367 4471 20950 84791 70958 1089 31565 98661 24025 22671 51156 30821 90587 48173...
output:
783485
result:
ok single line: '783485'
Test #35:
score: 0
Accepted
time: 0ms
memory: 5096kb
input:
333333 100 100 112231 202 59631 59756 59671 59699 59661 59727 59721 59743 59604 59704 59613 59710 59718 59779 59618 59784 59626 59629 59696 59729 59766 59742 59599 59611 59711 59761 59730 59751 59670 59667 59755 59746 59662 59786 59687 59595 59737 59790 59732 59600 59775 59723 59774 59605 59607 5969...
output:
16792960744
result:
ok single line: '16792960744'
Test #36:
score: 0
Accepted
time: 3ms
memory: 5156kb
input:
50000 100 100 50 202 13807 18302 7822 41564 28370 36614 47713 45687 40814 41680 15292 42480 1856 5026 24147 18557 14602 46726 47397 48107 14881 23577 49213 38587 25723 4789 16102 15467 15544 35794 28216 34134 34612 14911 6759 32693 45269 31753 14805 48280 5515 956 24835 45259 10732 43412 35798 9237 ...
output:
1215931
result:
ok single line: '1215931'
Test #37:
score: 0
Accepted
time: 3ms
memory: 5100kb
input:
50000 100 100 50 202 25546 22474 457 46882 5430 7874 32456 15680 16590 20930 1040 20627 28109 29496 44654 31602 23107 26024 19818 5021 49471 28106 7959 3350 21444 47345 39551 48660 42745 44325 39741 47544 39843 6283 28670 14657 19463 15502 18450 38489 6549 19656 14092 47259 39291 34875 35705 16887 4...
output:
1208992
result:
ok single line: '1208992'
Subtask #3:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #38:
score: 25
Accepted
time: 2ms
memory: 5168kb
input:
16016016 2000 2000 4161 4002 13370998 11661770 6190539 15811543 7208594 2287839 8357215 590986 15984007 9878726 4398741 1127736 11336806 461345 2915606 12889202 1514551 9872923 14002268 6698799 4382118 12385365 6011913 4440769 349275 10813747 680022 14976682 5731999 8091453 4923876 4486488 7375962 5...
output:
19783487252
result:
ok single line: '19783487252'
Test #39:
score: 0
Accepted
time: 0ms
memory: 5164kb
input:
17160249 2000 2000 5000 4002 7775887 13570785 10109057 3029521 12286149 7611815 3397711 9480753 2561297 5358697 6167103 6399221 872461 12814431 764411 7475767 6723393 11573819 6191131 14943507 13166621 9388735 4458273 12022055 10893493 7751925 2397251 15079591 3857985 11033573 10961539 9724923 13518...
output:
29961040351
result:
ok single line: '29961040351'
Test #40:
score: 0
Accepted
time: 0ms
memory: 5176kb
input:
1000000000000 2000 2000 1000000 4002 562333246111 335015960271 667985113649 58713582127 549479014215 928450409219 829996606921 163974178131 896284606361 252508483165 696482863419 932304887507 178708025383 526076766957 857178935309 962588645827 601855749519 161808011609 564446834413 22971143871 78281...
output:
3609199036570040
result:
ok single line: '3609199036570040'
Test #41:
score: 0
Accepted
time: 4ms
memory: 5208kb
input:
17000000 2000 2000 1 4002 4973616 10555439 12272010 16997605 5069646 16996623 16996532 4133345 4313406 16997085 16997323 4865582 2740878 16341404 10375374 16996699 16996648 16997506 2932941 16996886 14216670 628206 13532439 16997361 304100 8034608 11839881 8886896 1072336 16996535 16997054 12512098 ...
output:
7774981
result:
ok single line: '7774981'
Test #42:
score: 0
Accepted
time: 4ms
memory: 5380kb
input:
33333333 2000 2000 16 4002 26714666 33333302 5566236 29951955 7062831 3969585 27138845 33333317 33333217 22516987 5866354 33333048 1160453 33328850 7486994 16090418 15230079 32753096 4109647 33333292 25098025 21208458 27995183 6842737 24629824 14689864 8483393 14513787 19795902 33329182 7647058 2142...
output:
242702610
result:
ok single line: '242702610'
Test #43:
score: 0
Accepted
time: 2ms
memory: 5204kb
input:
20000000 1523 1999 53 3524 19998943 4073092 7501419 19998779 14530631 10175740 13043796 472122 3974434 3340219 15932973 7772714 1229671 331192 9774059 19998871 12000880 155021 7060987 1849810 19998926 19748801 12811245 11715476 19998856 19932011 17127407 6430275 8244846 18681218 1779342 6927097 1999...
output:
529162980
result:
ok single line: '529162980'
Test #44:
score: 0
Accepted
time: 0ms
memory: 5164kb
input:
1000000000000 2000 2000 1 4002 903598441823 800701107280 329671071842 548952284792 476025051684 587913415477 417583361671 28471592560 245255301367 565935348019 528972227834 625875542896 883618376857 206793672345 212288198213 232268259154 519981190592 204795673853 385115760095 123376909148 5594418269...
output:
264699919493
result:
ok single line: '264699919493'
Test #45:
score: 0
Accepted
time: 1ms
memory: 5208kb
input:
30000000 2000 2000 1 4002 11240203 11496298 23068590 15945937 8135050 708276 22860502 29999085 7654875 2677006 27982457 28798762 5253970 11224196 17754619 28430628 29999172 4053515 14185314 10327860 11048131 19915432 19979457 21035840 6870579 2484939 22076237 11608343 17226410 8727260 804313 3957481...
output:
14501519
result:
ok single line: '14501519'
Test #46:
score: 0
Accepted
time: 4ms
memory: 5296kb
input:
100000000 2000 2000 1000000 4002 1 4005 8009 12013 16017 20021 24025 28029 32033 36037 40041 44045 48049 52053 56057 60061 64065 68069 72073 76077 80081 84085 88089 92093 96097 100101 104105 108109 112113 116117 120121 124125 128129 132133 136137 140141 144145 148149 152153 156157 160161 164165 1681...
output:
2048975001999
result:
ok single line: '2048975001999'
Test #47:
score: 0
Accepted
time: 2ms
memory: 5172kb
input:
100000000 2000 2000 36999 4002 52142059 85634799 45022505 46615303 48992493 4942481 33900955 74413203 81440717 2813425 78723363 95967983 18073057 98581293 22823435 29174611 52866453 10741403 45358705 59937993 79247645 34937503 78463257 26917499 36030055 81464763 13338719 7383745 4274193 47007551 241...
output:
1849871321738
result:
ok single line: '1849871321738'
Test #48:
score: 0
Accepted
time: 1ms
memory: 5152kb
input:
100000000000 2000 2000 5 4002 1251226705 85924799802 35070892085 64471356699 86531902907 42853724684 73376288655 23316519750 73266295012 62904323973 90088340387 37303595853 97989805937 22562534114 54446028936 1991425865 24158404559 74450205058 33605399349 84823259271 65517537521 45631354774 20786153...
output:
116663676077
result:
ok single line: '116663676077'
Test #49:
score: 0
Accepted
time: 1ms
memory: 5160kb
input:
444444444 2000 2000 444444 4002 180425991 180424741 180423839 180425173 180424088 180426059 180422588 180422561 180424451 180422996 180425852 180423910 180422177 180424430 180423854 180423217 180423845 180425957 180424274 180424050 180422630 180423034 180425958 180424023 180425306 180423614 18042553...
output:
40229664348760
result:
ok single line: '40229664348760'
Test #50:
score: 0
Accepted
time: 0ms
memory: 5172kb
input:
17000488 2000 2000 1000000 4002 13935042 6399027 2883263 2992984 9770657 4204713 12711311 12329823 8681855 316889 12449273 5146313 6247385 16212669 7468582 12780623 11480940 1833512 10221531 3696635 9608449 4296379 8832060 1830482 13448386 8830077 575096 7703266 9026723 4384485 11145642 4114150 7688...
output:
70750757930
result:
ok single line: '70750757930'
Test #51:
score: 0
Accepted
time: 4ms
memory: 5232kb
input:
17000488 2000 2000 1000000 4002 2435624 5999789 13185531 15107265 12322731 11518508 4239516 2512918 4296541 4830445 10178688 9305254 15686287 7567277 16010437 12402242 6568665 12532095 3453298 3578228 14719186 2416873 2912412 9938088 15443975 4572671 9383830 3401151 3829251 3522300 9146899 8026542 8...
output:
64567178798
result:
ok single line: '64567178798'
Subtask #4:
score: 29
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #52:
score: 29
Accepted
time: 122ms
memory: 12956kb
input:
200000000000 200000 200000 600103 400002 110104568808 171819087396 153579275763 3919156948 44861424598 186731569245 149496344510 97572698146 12915343623 73741598104 90338153812 4298821245 75793029029 22582856538 92564845068 150710592452 139824697958 162438172569 33378745268 10290539374 5613922589 13...
output:
104169813471848
result:
ok single line: '104169813471848'
Test #53:
score: 0
Accepted
time: 81ms
memory: 12936kb
input:
1000000000000 200000 200000 1000000 400002 858859094275 81875209377 616924284611 351071755357 394792773963 480713603567 347326536637 286771033863 741139705697 964192420957 207032635179 569896449491 804772423867 303209516067 990000150005 116818984123 959961199815 879935999693 938755493791 93830589154...
output:
140373567326436
result:
ok single line: '140373567326436'
Test #54:
score: 0
Accepted
time: 99ms
memory: 12888kb
input:
170000000000 200000 200000 1 400002 108815562889 101277137884 100199534273 146692489015 72365441268 66191420479 39056930202 169999671119 122742809233 93011510054 74958649831 163084543552 154156513880 169999692949 64271413962 169999678623 169999670296 169999748137 72718242411 24986883369 55019383323 ...
output:
66307156091
result:
ok single line: '66307156091'
Test #55:
score: 0
Accepted
time: 106ms
memory: 12864kb
input:
170000000000 200000 200000 1 400002 169999745656 169999705954 20936869552 130641235069 135323650757 143100876780 30828502509 91078303271 23928479571 169999743226 123480811159 116211186927 50141366701 6366421036 47038156387 23867279366 169999716377 169999743213 54690581965 41010536420 127612424911 75...
output:
79106495913
result:
ok single line: '79106495913'
Test #56:
score: 0
Accepted
time: 104ms
memory: 12868kb
input:
170000000000 200000 200000 1 400002 163312544038 169999729017 169999691114 169999749459 46970956512 8693229062 169999725316 80421067905 169999689352 128373227813 128369627798 77183457095 42389341135 169999731976 83470278174 76432254639 33163710287 169999763860 169999751466 134628848609 169999742562 ...
output:
84999999899
result:
ok single line: '84999999899'
Test #57:
score: 0
Accepted
time: 114ms
memory: 12924kb
input:
1000000000000 200000 200000 190 400002 3354415461 454436097684 122637365756 492391073003 253147568367 129195396061 370850911872 422955152399 844151896336 634590529350 424316758713 999999403983 608517608768 688041175852 343050783436 286600122739 35516963978 999999411068 234739883381 300446986688 4502...
output:
18151099025030
result:
ok single line: '18151099025030'
Test #58:
score: 0
Accepted
time: 113ms
memory: 12928kb
input:
200000000000 200000 200000 1 400002 84457881116 176315787219 128745228767 63999012860 181838205837 57599391558 43427344296 74014246426 52102173221 99925932787 36970122844 199999801751 166911356013 105264750709 37728525424 85433484369 199999813175 84550281396 186211020459 57434991036 63521411240 1349...
output:
99999999839
result:
ok single line: '99999999839'
Test #59:
score: 0
Accepted
time: 117ms
memory: 12892kb
input:
170000000000 200000 200000 1 400002 169999711368 31661305356 165298550912 104856749956 91158704079 105714752800 61083003744 105370351663 4460814951 40828136091 137823259609 77463058267 113446378419 169999710128 7915626337 169999678066 72633042178 133139643949 169999759146 169999706866 10110433644 96...
output:
79822469316
result:
ok single line: '79822469316'
Test #60:
score: 0
Accepted
time: 116ms
memory: 13068kb
input:
170000000000 200000 200000 1 400002 27852492544 169999718523 5208417204 169999740565 21336470857 155324116928 169999677630 116196786644 155486117496 169999693720 140942068938 24232080560 144561280865 169999757086 67243823764 150657301354 104671948251 88536694559 59776198833 132207239877 169999672355...
output:
69462719647
result:
ok single line: '69462719647'
Test #61:
score: 0
Accepted
time: 119ms
memory: 12840kb
input:
170000000000 200000 200000 1 400002 42324540682 7154823749 169999709067 169832166208 11896039475 169999756331 163203344126 84316280555 39738532086 169999733966 11011636508 169999724634 169999737236 88132293261 169999736637 169999652388 132299640940 146116487178 19261663841 66305420623 86070686403 16...
output:
79205338707
result:
ok single line: '79205338707'
Test #62:
score: 0
Accepted
time: 107ms
memory: 12932kb
input:
200000000000 200000 200000 6 400002 141998872986 196439054759 91227904152 112475174712 30885303420 199753865825 78509461731 80661468870 95808319447 155392917522 30925703566 37518925464 9790432767 69280631057 146249287011 106512355094 17503658571 24408481822 188296627627 39728932732 171872972687 3746...
output:
472143416394
result:
ok single line: '472143416394'
Test #63:
score: 0
Accepted
time: 91ms
memory: 19132kb
input:
1000000000000 200000 200000 1000000 400002 1 400005 800009 1200013 1600017 2000021 2400025 2800029 3200033 3600037 4000041 4400045 4800049 5200053 5600057 6000061 6400065 6800069 7200073 7600077 8000081 8400085 8800089 9200093 9600097 10000101 10400105 10800109 11200113 11600117 12000121 12400125 12...
output:
20004899975199999
result:
ok single line: '20004899975199999'
Test #64:
score: 0
Accepted
time: 89ms
memory: 12856kb
input:
1000000000000 200000 200000 1000000 400002 375455477269 672860164286 743642918199 514922974606 199918599593 219603898020 991570157833 337921689608 978486492417 555282776410 576472882361 308688743448 304892724469 703176315878 704920324599 272512962574 849516247577 634256371284 885258026287 9847457237...
output:
499999900013000000
result:
ok single line: '499999900013000000'
Test #65:
score: 0
Accepted
time: 97ms
memory: 12900kb
input:
400000000000 200000 200000 950 400002 111840159199 211621458105 394802774009 332122860613 77302386519 58555492788 32396961998 120271001368 388036740192 99135295694 314600373016 220432702182 66290731478 267692138482 299486697456 112430562182 289363846846 231408357072 166078030424 61565107864 36520782...
output:
189804669014079
result:
ok single line: '189804669014079'
Test #66:
score: 0
Accepted
time: 81ms
memory: 12896kb
input:
400000000000 200000 200000 900 400002 194830574149 75157975791 212298261491 153957969793 32156160789 147530737662 207133035674 356826184138 385108725552 290213451080 159177195904 380104700538 180331701680 75758378818 241647208260 125936229710 148634743204 369335046702 20878904432 2091210496 13168705...
output:
180000000000000
result:
ok single line: '180000000000000'
Test #67:
score: 0
Accepted
time: 95ms
memory: 12952kb
input:
400000000000 200000 200000 1100 400002 1822009111 146759133795 154397571989 342115710577 323700418503 71599958010 143186315942 14946474748 282219411108 44925424646 251281656424 277558587810 109220946128 366643433236 104121720636 273372566888 284401422034 97161685842 62329911686 65459127334 124800666...
output:
189993572473326
result:
ok single line: '189993572473326'
Test #68:
score: 0
Accepted
time: 100ms
memory: 12836kb
input:
400000000000 200000 200000 1800 400002 307885539421 94098070491 33724168625 338958094789 163760818809 185172925872 343554917780 331604058028 12832464180 35616178100 88075240396 323669218362 263126515652 376287481456 316210781076 165698828522 359673398392 323692818492 160231201190 375879879430 158258...
output:
190038584576031
result:
ok single line: '190038584576031'
Test #69:
score: 0
Accepted
time: 120ms
memory: 12868kb
input:
200000000000 200000 200000 1000 400002 32212702550 176635562139 182119990102 78943560403 105412536092 7228027268 45120605224 105616030516 173039559235 36039303377 106506573209 105969535551 119357273361 47447593881 23002668640 166613754396 34514854610 175091183184 104962575559 99003476804 11970742743...
output:
10025505140014
result:
ok single line: '10025505140014'
Test #70:
score: 0
Accepted
time: 107ms
memory: 12932kb
input:
200000000000 200000 200000 1000 400002 153663017314 12581997016 24891484751 78656996690 76627767203 2455312311 75594058795 145430070322 129893583475 185588098056 40484545827 152008483396 192668974080 87865251688 74362659995 141841563338 15462257269 167519599853 75364552815 68798438015 21292698889 10...
output:
10040242849536
result:
ok single line: '10040242849536'
Test #71:
score: 0
Accepted
time: 120ms
memory: 12952kb
input:
200000000000 200000 200000 1000 400002 192939170799 32217663815 178255477632 128170519966 196753834305 138481988640 51548377075 123211604517 78488161665 103350298426 75975095256 27386415424 76483272911 87053558559 178751863396 175718372701 168664586366 173850832908 184624556511 61941368526 120765845...
output:
10478774982465
result:
ok single line: '10478774982465'
Test #72:
score: 0
Accepted
time: 115ms
memory: 12956kb
input:
200000000000 200000 200000 1000 400002 129177114545 126499345946 120670053787 192741017623 125297279227 186735364939 183532733067 112090718605 32250779428 14341247899 184496501327 150535652394 155252223578 50145836218 115850572674 179634337394 186236142542 90614368695 120565255450 14518051822 109859...
output:
13715494706929
result:
ok single line: '13715494706929'
Test #73:
score: 0
Accepted
time: 111ms
memory: 12932kb
input:
200000000000 200000 200000 1000 400002 19572847485 20805453487 151605090802 131716327165 100967364150 40249547041 194794559890 198813790649 169031810455 104418760411 51575201343 93588880320 123315450331 103362820592 195382848953 134078198882 44165027053 189450052370 112347369366 134896601892 1682323...
output:
31325103176701
result:
ok single line: '31325103176701'
Test #74:
score: 0
Accepted
time: 91ms
memory: 12840kb
input:
200000000000 200000 200000 1000 400002 45906569177 127728588007 193327197727 96017504291 151709655403 23482355022 43719244839 174011044164 52216455689 47088814963 172154245379 126433385100 167267628415 1031257693 185921264880 11782987624 115450815783 31192677833 143859095285 64704011512 147217657866...
output:
63743950940997
result:
ok single line: '63743950940997'
Test #75:
score: 0
Accepted
time: 139ms
memory: 12892kb
input:
200000000000 200000 200000 1000 400002 151300352413 143801686847 21465873725 138016128706 124872256541 137682867229 185404014327 33531138729 169433648728 48842843023 94314139596 178679399132 161019321014 198581383017 51852887220 196847576168 38379104761 154266076077 132684208588 65116442814 70999675...
output:
92372468373112
result:
ok single line: '92372468373112'
Test #76:
score: 0
Accepted
time: 162ms
memory: 12900kb
input:
200000000000 200000 200000 1000 400002 85414871981 126917682658 33946759408 48839151973 72146589469 88103853822 104993639034 33387005053 167620915648 12460321043 18467672488 187222631200 25403481058 30230646517 86021984031 51187358055 89533576298 3582443438 15280709827 76549135585 140220518437 12101...
output:
99998408211058
result:
ok single line: '99998408211058'
Test #77:
score: 0
Accepted
time: 114ms
memory: 12948kb
input:
222222222222 200000 200000 1000 400002 69234853422 69234856118 69235052340 69234764130 69235075453 69234864531 69234789632 69235039591 69235001236 69234970849 69235024950 69235102506 69234826115 69234857683 69234954100 69234806546 69234978493 69234793398 69234996227 69234781642 69235012306 692351238...
output:
44638735419846
result:
ok single line: '44638735419846'
Test #78:
score: 0
Accepted
time: 107ms
memory: 13104kb
input:
222222222222 200000 200000 1000 400002 206263373934 206263143831 206263239487 206263204553 206263261597 206263381053 206263271180 206263082774 206263269911 206263411813 206263054768 206263068653 206263225878 206263305128 206263421138 206263150330 206263078536 206263369896 206263051415 206263206768 2...
output:
110452793598584
result:
ok single line: '110452793598584'
Test #79:
score: 0
Accepted
time: 109ms
memory: 12868kb
input:
222222311099 200000 200000 1000000 400002 155810837092 48811013365 56186317569 177779892671 167036923689 66674762708 6133487333 132969318758 163901659086 217167415562 61703253093 712399518 66562586492 111043030227 66258953441 196006510567 12446238136 83731810354 127922944342 40350100558 110524465664...
output:
9791570077751
result:
ok single line: '9791570077751'
Test #80:
score: 0
Accepted
time: 118ms
memory: 12936kb
input:
222222311099 200000 200000 1000000 400002 51526976536 12711521830 200744558232 194140398085 147509495894 53106360703 194631110239 178955074434 33619498834 203719230056 28385639724 92821360886 118561963279 106534676999 143303457347 190076004179 193581225537 57485089525 42833303016 210547481875 422669...
output:
8168746223892
result:
ok single line: '8168746223892'
Extra Test:
score: 0
Extra Test Passed