QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87530 | #2420. Kitesurfing | yyyyxh | AC ✓ | 443ms | 39548kb | C++14 | 1.4kb | 2023-03-13 16:29:37 | 2023-03-13 16:29:45 |
Judging History
answer
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=503;
__gnu_pbds::gp_hash_table<int,ll> mp;
int s,d,t,n,dt;
void chmn(ll &x,ll v){if(x>v) x=v;}
ll calc(int x){
if(x<0) return 0;
ll res=x;
chmn(res,(ll)(x+d-1)/d*t);
chmn(res,(ll)(x/d)*t+x%d);
return res;
}
int l[N],r[N];
ll dfs(int x){
if(x>=s) return 0;
if(mp.find(x)!=mp.end()) return mp[x];
int pos=lower_bound(l+1,l+n+1,x)-l;
if(pos>n) return mp[x]=calc(s-x);
ll res=INF;
if(x+d<=l[pos]){
int t=(l[pos]-x)/d;
chmn(res,dfs(x+t*d)+(ll)t*dt);
}
else{
int ver=x+d;
int o=upper_bound(r+1,r+n+1,ver)-r;
if(o<=n&&l[o]<ver) ver=l[o];
chmn(res,dfs(ver)+t);
}
for(int i=pos;i<=n;++i){
if(l[i]-d>l[pos]) break;
if(l[i]>x) chmn(res,dfs(l[i])+calc(l[i]-d-x)+t);
if(r[i]-d>l[pos]) break;
if(r[i]>x) chmn(res,dfs(r[i])+calc(r[i]-d-x)+t);
}
return mp[x]=res;
}
int main(){
//freopen("kun.in","r",stdin);
//freopen("kun.out","w",stdout);
s=read();d=read();t=read();n=read();dt=t;if(d<dt) dt=d;
for(int i=1;i<=n;++i){l[i]=read();r[i]=read();}
printf("%lld\n",dfs(0));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 2844kb
input:
10 4 5 0
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 2ms
memory: 2844kb
input:
10 4 1 0
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 2916kb
input:
10 4 3 0
output:
8
result:
ok single line: '8'
Test #4:
score: 0
Accepted
time: 1ms
memory: 2860kb
input:
4 2 1 1 2 3
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 2884kb
input:
18 10 11 2 3 5 7 14
output:
23
result:
ok single line: '23'
Test #6:
score: 0
Accepted
time: 1ms
memory: 2880kb
input:
1000000000 100 90 0
output:
900000000
result:
ok single line: '900000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 2828kb
input:
697 310 191 1 384 497
output:
459
result:
ok single line: '459'
Test #8:
score: 0
Accepted
time: 0ms
memory: 2856kb
input:
337489234 846388201 210392939 3 63127010 66068111 137080824 196209361 222495016 320924100
output:
210392939
result:
ok single line: '210392939'
Test #9:
score: 0
Accepted
time: 2ms
memory: 2788kb
input:
10 4 3 1 8 9
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 2ms
memory: 2860kb
input:
20 5 1 4 3 6 9 12 13 14 16 18
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 2ms
memory: 2916kb
input:
33030012 846831 33589 39 161 845994 846322 1692906 1693528 2540025 2540916 3387100 3388072 4234575 4234724 5081265 5082139 5928664 5928757 6774943 6775186 7621539 7622286 8468627 8469012 9315723 9316381 10162503 10162589 11008927 11009763 11855714 11856173 12702595 12703320 13549158 13549619 1439643...
output:
1316718
result:
ok single line: '1316718'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3004kb
input:
16402055 52929 20498 310 682 53041 53330 105659 106127 158313 158555 210588 210683 262653 263552 315903 316339 368368 369016 421340 421430 474340 474720 527035 527601 580020 580694 633214 633293 685739 686700 739471 740043 792705 793505 846126 846245 898627 898897 951544 951790 1004434 1004438 10566...
output:
6376311
result:
ok single line: '6376311'
Test #13:
score: 0
Accepted
time: 0ms
memory: 2840kb
input:
13153613 692256 91753 19 559 691928 692102 1383372 1384161 2075581 2076566 2768565 2768838 3460562 3461196 4152671 4153436 4844918 4845111 5536419 5537285 6229200 6229277 6921310 6921965 7613605 7614210 8305940 8306367 8998200 8999129 9690640 9690727 10382841 10383328 11075429 11075713 11767874 1176...
output:
1745083
result:
ok single line: '1745083'
Test #14:
score: 0
Accepted
time: 2ms
memory: 2996kb
input:
82115478 203242 69057 404 262 202564 203528 406080 407051 609666 610451 812905 813117 1016319 1016840 1220048 1220581 1423262 1424199 1626507 1626634 1829488 1830375 2033146 2033679 2235945 2236278 2438593 2439061 2642025 2642265 2844846 2845079 3048133 3048374 3250757 3251120 3453756 3454629 365767...
output:
27940099
result:
ok single line: '27940099'
Test #15:
score: 0
Accepted
time: 0ms
memory: 2996kb
input:
29335567 116846 40442 251 225 116409 116439 232649 233560 350204 350230 467023 467878 584662 585109 701637 702441 818761 819270 935236 935945 1052503 1053243 1169292 1170209 1286614 1287286 1403776 1404001 1520216 1520856 1637360 1638327 1754500 1754932 1870801 1871003 1987200 1988083 2104665 210500...
output:
10177681
result:
ok single line: '10177681'
Test #16:
score: 0
Accepted
time: 2ms
memory: 2972kb
input:
218600004 437224 85101 500 888 437805 438464 875298 875777 1312070 1312484 1749025 1749857 2186435 2187013 2623340 2623461 3060491 3061198 3497959 3498077 3934649 3935509 4372102 4372609 4809085 4810077 5247054 5247613 5683976 5684304 6120781 6121714 6558148 6558541 6995273 6995554 7431884 7432864 7...
output:
42590274
result:
ok single line: '42590274'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3024kb
input:
128831209 257660 63190 500 625 257686 258082 515262 516103 772873 773239 1030295 1030812 1287752 1288307 1545114 1545897 1803275 1803405 2060563 2061516 2319019 2319686 2577066 2577610 2835055 2835193 3092685 3092766 3350294 3351210 3608490 3609288 3866029 3866311 4122988 4123012 4380060 4380557 463...
output:
31641939
result:
ok single line: '31641939'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3036kb
input:
125276177 250560 78140 500 722 250916 251038 501352 502257 752157 752879 1002578 1003495 1253174 1253746 1503673 1504045 1753687 1754095 2003776 2004670 2254534 2255150 2505200 2505332 2755553 2755766 3006161 3006336 3256063 3256430 3506057 3506335 3756554 3757506 4007077 4007115 4257400 4257701 450...
output:
39109343
result:
ok single line: '39109343'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3168kb
input:
264371637 528764 97681 500 103 528526 529466 1057762 1058174 1586289 1587208 2115830 2116164 2644422 2645204 3173225 3173840 3701659 3702461 4230701 4230729 4759043 4759595 5287391 5288094 5816467 5816597 6344423 6344586 6872911 6873806 7402394 7402429 7931181 7931579 8460107 8460237 8988622 8988652...
output:
48882951
result:
ok single line: '48882951'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3076kb
input:
252544224 505102 36816 500 380 504514 504703 1009498 1009539 1514049 1514260 2018369 2018802 2522952 2523138 3027494 3027802 3532040 3532505 4036787 4037590 4542239 4543134 5047894 5048686 5553247 5553678 6057856 6058257 6562630 6562695 7066882 7067812 7572528 7573304 8077696 8077735 8582050 8582501...
output:
18447578
result:
ok single line: '18447578'
Test #21:
score: 0
Accepted
time: 0ms
memory: 2904kb
input:
44889530 221464 52660 75 70401 130674 812086 826693 897081 1107861 1946062 2116748 2318239 2412590 3040677 3136502 3904286 4081784 4879978 5039656 5224799 5370041 5418855 5578091 6101958 6104689 6532762 6719409 7090342 7183005 7781076 7972270 8706353 8709684 9446847 9507548 10207293 10302521 1050608...
output:
11269189
result:
ok single line: '11269189'
Test #22:
score: 0
Accepted
time: 2ms
memory: 2932kb
input:
86204666 448388 97029 112 517922 694024 1387052 1684094 2352065 2505911 3324325 3369492 4041426 4385682 4421019 4842235 5559214 5563348 6313251 6704318 7314907 7364138 7440064 7881587 8336388 8655108 9590611 9619171 10594824 10862984 11769200 12042218 12776000 12968487 13625608 13977934 14890956 149...
output:
19752429
result:
ok single line: '19752429'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3072kb
input:
91230621 97619 86852 166 19156 99725 214471 222831 235282 287988 1144510 1160898 2109974 2130488 2858577 2859531 3813419 3899179 4473871 4495007 5389236 5435511 5968990 5988414 6483629 6527753 6616010 6630567 7505568 7559362 7988812 8036750 8782579 8828488 9001606 9041092 9934314 9938446 10252377 10...
output:
81366245
result:
ok single line: '81366245'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3012kb
input:
139347242 728570 94658 160 877847 1601328 2467030 2848194 3126886 3726312 4350042 4493421 4796920 4942979 5845974 5924773 6044859 6702414 7676564 8178448 8347943 9025942 9499422 10180346 10971872 11371199 12333966 12456756 13193851 13770446 14517617 14934697 15882406 16047977 16385684 16849717 16945...
output:
20169336
result:
ok single line: '20169336'
Test #25:
score: 0
Accepted
time: 2ms
memory: 2968kb
input:
324735229 603784 27103 398 233946 323574 1125853 1169628 1775439 2288407 2881555 3117313 3482485 4015581 4981433 5191038 5340296 5387233 5653158 5659044 6422194 6987564 7133283 7150586 7914957 8285043 8882861 9200955 9761672 10345739 10689004 11124206 12105218 12512885 13289425 13893027 14522713 146...
output:
16340034
result:
ok single line: '16340034'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3132kb
input:
249389677 35898 16003 500 354001 389145 535670 549622 838918 858654 1627606 1636022 2165452 2194987 3007552 3043222 3349372 3381591 3433813 3436668 4230796 4239639 4693985 4723032 4760610 4779029 4897667 4926790 5496687 5502265 6118804 6129841 6357047 6362586 6765658 6773278 7351220 7384690 7410489 ...
output:
111879229
result:
ok single line: '111879229'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3040kb
input:
411211856 638730 18810 500 358472 360688 742763 1147660 1171421 1662785 2270051 2829430 3154110 3234662 3242014 3401770 3442885 4043182 5004459 5145554 5906577 6534148 7018947 7397440 7762743 7913979 8750870 8950893 9357424 9773326 10545184 10595050 10924840 11007922 11012963 11452523 11739501 12077...
output:
13521259
result:
ok single line: '13521259'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3064kb
input:
289363541 171007 57363 500 701600 830827 1082166 1107812 1671382 1832485 2528190 2589602 2639312 2719789 3106328 3210155 3369962 3419882 4014903 4182748 4965431 5051340 5309387 5475370 6362912 6445282 6593775 6708324 7162828 7235936 7834048 7995601 8151703 8174743 8571678 8583346 8997452 9158295 942...
output:
100102836
result:
ok single line: '100102836'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3044kb
input:
348124465 435147 55152 500 136729 212989 902824 916704 1870211 1894033 2394699 2488555 2889876 3244030 3582336 3746625 4189616 4226767 4242408 4411667 5100151 5511590 5615938 5867473 6765777 6953728 7938682 8210056 9022386 9169760 9991752 10001108 10058820 10096700 10849609 10850478 11709377 1203580...
output:
48012413
result:
ok single line: '48012413'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3020kb
input:
491037840 952485 63644 500 762495 984339 1749053 1774913 2510081 3059530 3747204 4050572 4921770 4968015 5552500 6175262 6383350 6780802 6917891 7408018 7995409 8042369 8865821 9251505 9632554 10330894 10688549 11107272 11270009 11760290 12646891 13291849 13589167 13713550 13770362 13771170 14180005...
output:
37804990
result:
ok single line: '37804990'
Test #31:
score: 0
Accepted
time: 1ms
memory: 2852kb
input:
1 12345678 55555 0
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 1ms
memory: 2832kb
input:
1000000000 1000000000 1000000000 2 1 2 999999998 999999999
output:
1000000000
result:
ok single line: '1000000000'
Test #33:
score: 0
Accepted
time: 1ms
memory: 2832kb
input:
9402 1901 629 7 326 429 1690 2318 3141 3506 4822 5234 6622 6782 7125 7968 8450 9076
output:
3720
result:
ok single line: '3720'
Test #34:
score: 0
Accepted
time: 2ms
memory: 2872kb
input:
992770102 54000399 809021161 92 653688 1765846 3911506 4829819 6493949 7687640 13009618 18861637 21802043 22982267 23805432 26327369 31689288 39232847 42193343 56233498 57170807 80334087 83467848 84423120 87688537 89969817 90002263 90651407 90732628 91729582 101360583 110521255 113466307 118636834 1...
output:
14598184565
result:
ok single line: '14598184565'
Test #35:
score: 0
Accepted
time: 0ms
memory: 2872kb
input:
800322226 30037588 57192627 39 14469726 15768930 54395007 57341487 80835052 88906251 93859267 111388922 122194457 127463056 133508465 141010122 144275312 155870559 156938007 157728907 164717583 165672817 181807664 193010010 194241313 205907771 214857530 218260818 231928225 233773366 249368675 263628...
output:
1512995612
result:
ok single line: '1512995612'
Test #36:
score: 0
Accepted
time: 2ms
memory: 2828kb
input:
1000000000 1 1000000000 1 2019 2020
output:
1999999999
result:
ok single line: '1999999999'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3012kb
input:
1000000000 1 1000000000 500 1181322 1181323 7587543 7587544 8404676 8404677 10602085 10602086 11438615 11438616 14675969 14675970 14749907 14749908 19647863 19647864 22545422 22545423 27617786 27617787 29354035 29354036 29452587 29452588 31429207 31429208 35346320 35346321 36586491 36586492 37963658...
output:
500999999500
result:
ok single line: '500999999500'
Test #38:
score: 0
Accepted
time: 2ms
memory: 2892kb
input:
500 92 80 2 370 371 374 466
output:
440
result:
ok single line: '440'
Test #39:
score: 0
Accepted
time: 2ms
memory: 3068kb
input:
603652831 92182 79700 499 569615 661797 1426375 1443807 2606040 2698222 3708027 3800209 3956863 4019759 4600671 4692853 5598456 5690638 6593660 6685842 7771206 7863388 7996120 8088302 9272767 9364949 12287578 12379760 12883581 12975763 15031519 15123701 17762476 17854658 19053357 19084281 19802274 1...
output:
524475166
result:
ok single line: '524475166'
Test #40:
score: 0
Accepted
time: 7ms
memory: 3076kb
input:
613855482 710477294 400400 500 342383 1548550 2124080 2247135 2529358 4723082 4871760 5085461 5113782 5533316 6040336 6406121 7128379 7406845 7512232 8075275 8440075 8460292 8745283 9128705 9349563 10946236 11524983 11847452 13595300 13878134 14522006 15892866 17247380 17408112 17594348 18842007 199...
output:
400400
result:
ok single line: '400400'
Test #41:
score: 0
Accepted
time: 2ms
memory: 3080kb
input:
588812180 1 25204 500 637775 637776 2267851 2267852 3400618 3400619 4293914 4293915 4711720 4711721 6510739 6510740 8569605 8569606 8922544 8922545 9572739 9572740 9981641 9981642 10490383 10490384 12875328 12875329 15181680 15181681 15851896 15851897 18145240 18145241 19437236 19437237 21646271 216...
output:
601413680
result:
ok single line: '601413680'
Test #42:
score: 0
Accepted
time: 2ms
memory: 2848kb
input:
1000000000 900000000 1 0
output:
2
result:
ok single line: '2'
Test #43:
score: 0
Accepted
time: 1ms
memory: 2980kb
input:
962584562 900174016 733116 227 878544 1340391 1860029 16567047 20422840 21260397 22017535 22332347 25489177 26327799 29619531 31639588 33902136 39067263 39577849 39717006 43705028 50627133 51766113 54382839 56827920 57089523 58453632 61862883 63967565 65196472 65872238 66547669 67819949 71719630 726...
output:
1466232
result:
ok single line: '1466232'
Test #44:
score: 0
Accepted
time: 2ms
memory: 3112kb
input:
744323767 409635357 755390164 358 149668 701023 818671 2235636 2489893 5914990 7720361 9204564 9706727 9861098 10037564 10250250 13886564 14000343 14257826 14540843 14848584 16655413 16779518 17202639 18466783 19307826 20382423 21252263 26569313 26844181 27717398 30095783 30286363 30436100 31317394 ...
output:
1510780328
result:
ok single line: '1510780328'
Test #45:
score: 0
Accepted
time: 4ms
memory: 2988kb
input:
497646495 819273811 239655936 313 166685 190067 1166654 1829652 1957003 4788831 5438543 5464114 7595425 8278328 10166883 10699926 11037480 11332085 11338292 13018775 13474561 13933736 14362820 14896076 15909281 17526379 17690754 18375183 19593911 20914193 21254877 23662899 25669810 28229091 28425155...
output:
239655936
result:
ok single line: '239655936'
Test #46:
score: 0
Accepted
time: 3ms
memory: 3108kb
input:
677230570 202014519 362473519 198 5340091 7654239 9088831 12725343 13118367 13674783 14150898 15270684 15811478 17383054 18192351 19113281 19615174 20046687 21092660 21200300 21260942 24724039 24798895 27326041 30753492 31323568 34785014 35721120 36529896 37553850 40209988 41124941 42851468 45274288...
output:
1449894076
result:
ok single line: '1449894076'
Test #47:
score: 0
Accepted
time: 4ms
memory: 3140kb
input:
845869577 971697686 654205366 339 59835 3239079 6445571 8894272 9517868 9596500 11220407 11971604 12140706 12446749 13395186 13510706 13888457 17690489 17883343 18074624 18220102 18338626 18516393 18804998 19445249 21010515 22376983 22520904 27855724 28515822 29637729 30488998 30659259 30967065 3113...
output:
654205366
result:
ok single line: '654205366'
Test #48:
score: 0
Accepted
time: 1ms
memory: 2856kb
input:
727128871 208499269 610129788 25 9594659 14966462 16856684 39184187 49173276 56939448 102691559 137386264 159016790 162203226 164684564 165881303 190076459 230808964 248534092 249396783 249629483 259847866 284852326 287358106 299229339 312363544 314723336 320649030 324167429 339555188 342891922 3547...
output:
2440519152
result:
ok single line: '2440519152'
Test #49:
score: 0
Accepted
time: 4ms
memory: 2992kb
input:
784831258 867436900 867198226 454 456575 763798 2776970 2991918 4175091 5624962 6621910 6698611 7247170 7473782 8147227 8343002 10789044 10853275 13587994 14274231 14447245 15149192 15680864 16207724 18454451 18988283 19477793 21633191 23145752 26305196 26586829 27180343 30353784 30920833 32775461 3...
output:
867198226
result:
ok single line: '867198226'
Test #50:
score: 0
Accepted
time: 0ms
memory: 2980kb
input:
4167869 564106823 194273417 164 21464 24664 46022 65698 83461 84752 89515 102520 105103 124740 125492 135143 143883 152511 160259 168241 182638 187298 191029 194978 247529 249123 254347 264057 272397 292057 302189 307777 309529 340733 345567 377920 378753 389907 391143 395305 411412 416409 423770 43...
output:
194273417
result:
ok single line: '194273417'
Test #51:
score: 0
Accepted
time: 2ms
memory: 2972kb
input:
797928239 289205030 980483881 212 221053 731302 1514582 3535996 4042274 5208520 7372905 11825037 12317664 12321916 13734393 14930963 15935952 16388885 17708477 23354416 25165139 26368613 28834539 28910284 29627449 31150046 36149154 36294144 36477849 37783098 41719535 42897153 46786172 50747972 50776...
output:
2941451643
result:
ok single line: '2941451643'
Test #52:
score: 0
Accepted
time: 3ms
memory: 3024kb
input:
692435277 407268360 467114411 243 1043613 1205356 2719533 5568427 7427650 9253632 9661377 10905697 12336244 16851382 17509255 17603321 17785512 18155026 18818547 20609848 23196163 25377936 27230663 28666068 36054645 37492649 38621757 39632754 40914703 41256370 44421822 45457885 47470993 51680082 522...
output:
934228822
result:
ok single line: '934228822'
Test #53:
score: 0
Accepted
time: 2ms
memory: 2852kb
input:
408728984 331742404 788063806 64 756116 2370271 3033458 6082988 7396575 7741884 16010003 20269865 21471657 24544184 25400487 25492995 26543804 31119756 33042812 35196561 40511949 47600278 47827874 50088848 52571651 53490118 55611224 59051467 59577010 60146861 64624168 66672550 71211693 71787223 7871...
output:
1576127612
result:
ok single line: '1576127612'
Test #54:
score: 0
Accepted
time: 443ms
memory: 39548kb
input:
1000000000 10000 5000 500 10042 10043 30044 30045 50046 50047 70048 70049 90050 90051 110052 110053 130054 130055 150056 150057 170058 170059 190060 190061 210062 210063 230064 230065 250066 250067 270068 270069 290070 290071 310072 310073 330074 330075 350076 350077 370078 370079 390080 390081 4100...
output:
500000000
result:
ok single line: '500000000'
Test #55:
score: 0
Accepted
time: 2ms
memory: 2884kb
input:
17 6 1000 2 1 2 15 16
output:
2005
result:
ok single line: '2005'
Test #56:
score: 0
Accepted
time: 1ms
memory: 2828kb
input:
23 6 1000 2 1 2 21 22
output:
2011
result:
ok single line: '2011'
Test #57:
score: 0
Accepted
time: 1ms
memory: 2860kb
input:
599999900 200000000 1000000000 2 1 2 599999898 599999899
output:
2199999900
result:
ok single line: '2199999900'
Test #58:
score: 0
Accepted
time: 1ms
memory: 2848kb
input:
599999900 200000000 1 2 1 2 599999898 599999899
output:
3
result:
ok single line: '3'
Test #59:
score: 0
Accepted
time: 1ms
memory: 2860kb
input:
400000001 200000000 1000000000 2 1 2 399999999 400000000
output:
2000000001
result:
ok single line: '2000000001'
Test #60:
score: 0
Accepted
time: 2ms
memory: 2856kb
input:
400000001 200000000 1 2 1 2 399999999 400000000
output:
3
result:
ok single line: '3'