QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138428 | #366. Long Distance Coach | Rafi22# | 71 | 11ms | 11860kb | C++14 | 1.8kb | 2023-08-11 18:17:01 | 2024-07-04 01:37:01 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=100000000000000007;
int mod=1000000007;
int mod1=998244353;
const int N=200007;
map<int,vector<int>>M;
vector<pair<int,int>>W[N];
int DP[N];
int val[N];
void add(int l,int r,int c)
{
// cout<<"JEST "<<l<<" "<<r<<" "<<c<<endl;
W[r].pb({l,c});
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x,n,m,w,t;
cin>>x>>n>>m>>w>>t;
int ans=x/t+1;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
M[a/t].pb(a%t);
}
M[x/t].pb(x%t);
vector<pair<int,int>>C(m+1);
C[0].st=-inf;
for(int i=1;i<=m;i++)
{
cin>>C[i].st>>C[i].nd;
ans+=(x-C[i].st)/t+1;
}
ans*=w;
sort(all(C));
for(auto [p,y]:M)
{
vector<int>V=y;
sort(all(V));
int l=1;
for(auto i:V)
{
int r=--lower_bound(all(C),make_pair(i,0LL))-C.begin();
if(l<=r) add(l,r,p);
l=r+1;
}
}
for(int i=1;i<=m;i++) val[i]=inf;
for(int i=1;i<=m+1;i++)
{
int S=0;
DP[i]=inf;
for(int j=i-1;j>=0;j--)
{
DP[i]=min(DP[i],DP[j]+S);
if(val[j]==inf) break;
S+=C[j].nd;
S-=((x-C[j].st)/t+1-val[j])*w;
}
for(auto [l,c]:W[i])
{
for(int j=l;j<=i;j++) val[j]=min(val[j],c);
}
}
cout<<ans+DP[m+1]<<endl;
return 0;
}
/*
19 1 4 8 7
10
1 20
2 10
4 5
6 5
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 16
Accepted
Test #1:
score: 16
Accepted
time: 2ms
memory: 9656kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 0
Accepted
time: 2ms
memory: 10420kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: 0
Accepted
time: 0ms
memory: 11080kb
input:
5 1 1 15 4 3 2 13
output:
43
result:
ok single line: '43'
Test #4:
score: 0
Accepted
time: 2ms
memory: 11176kb
input:
5 1 1 15 4 3 2 19
output:
45
result:
ok single line: '45'
Test #5:
score: 0
Accepted
time: 0ms
memory: 10328kb
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: 2ms
memory: 10848kb
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: 2ms
memory: 10380kb
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: 2ms
memory: 10804kb
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: 11256kb
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: 0ms
memory: 9844kb
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: 0ms
memory: 10068kb
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: 2ms
memory: 9864kb
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: 2ms
memory: 10596kb
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: 10996kb
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: 9524kb
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: 2ms
memory: 10784kb
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: 0ms
memory: 11336kb
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: 2ms
memory: 10728kb
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: 0ms
memory: 11352kb
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: 2ms
memory: 9952kb
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: 0ms
memory: 11372kb
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: 2ms
memory: 9452kb
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: 11320kb
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: 2ms
memory: 10784kb
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: 0ms
memory: 10152kb
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: 2ms
memory: 9332kb
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: 2ms
memory: 11108kb
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: 2ms
memory: 10648kb
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: 0ms
memory: 10632kb
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: 2ms
memory: 9480kb
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: 0ms
memory: 10396kb
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: 0ms
memory: 9720kb
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: 2ms
memory: 10964kb
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: 2ms
memory: 10816kb
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: 10264kb
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: 0ms
memory: 9564kb
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: 0ms
memory: 10892kb
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: 3ms
memory: 9988kb
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: 11ms
memory: 11508kb
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: 7ms
memory: 11336kb
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: 3ms
memory: 10880kb
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: 8ms
memory: 11860kb
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: 7ms
memory: 11180kb
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: 4ms
memory: 10752kb
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: 7ms
memory: 9664kb
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: 10ms
memory: 11488kb
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: 7ms
memory: 10060kb
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: 8ms
memory: 11520kb
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: 6ms
memory: 11000kb
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: 3ms
memory: 9932kb
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: 8ms
memory: 11360kb
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: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #52:
score: 0
Time Limit Exceeded
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...