QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138440#366. Long Distance CoachRafi22#46 9ms11892kbC++141.7kb2023-08-11 18:29:442024-07-04 01:37:02

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 01:37:02]
  • 评测
  • 测评结果:46
  • 用时:9ms
  • 内存:11892kb
  • [2023-08-11 18:29:44]
  • 提交

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=1000000000007;
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);
            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
*/

详细

Subtask #1:

score: 16
Accepted

Test #1:

score: 16
Accepted
time: 2ms
memory: 10188kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

score: 0
Accepted
time: 0ms
memory: 10112kb

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

score: 0
Accepted
time: 1ms
memory: 10436kb

input:

5 1 1 15 4
3
2 13

output:

43

result:

ok single line: '43'

Test #4:

score: 0
Accepted
time: 1ms
memory: 10064kb

input:

5 1 1 15 4
3
2 19

output:

45

result:

ok single line: '45'

Test #5:

score: 0
Accepted
time: 2ms
memory: 11148kb

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: 9536kb

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: 10028kb

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: 11068kb

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: 11232kb

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: 10352kb

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: 10716kb

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: 0ms
memory: 9620kb

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: 1ms
memory: 10492kb

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: 2ms
memory: 11192kb

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: 1ms
memory: 9968kb

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: 10292kb

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: 1ms
memory: 10764kb

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: 1ms
memory: 9784kb

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: 10124kb

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: 0ms
memory: 10284kb

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: 11132kb

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: 1ms
memory: 10644kb

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: 1ms
memory: 10384kb

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: 10740kb

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: 10464kb

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: 1ms
memory: 9756kb

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: 1ms
memory: 10312kb

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: 9816kb

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: 1ms
memory: 9900kb

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: 0ms
memory: 9980kb

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: 9576kb

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: 9964kb

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: 1ms
memory: 10500kb

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: 1ms
memory: 10180kb

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: 1ms
memory: 9464kb

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: 1ms
memory: 9608kb

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: 10932kb

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: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #38:

score: 25
Accepted
time: 6ms
memory: 9880kb

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: 9ms
memory: 10164kb

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: 9ms
memory: 10020kb

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: 9ms
memory: 10908kb

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: 9ms
memory: 9712kb

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: 9ms
memory: 10928kb

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: 9ms
memory: 10912kb

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: 9ms
memory: 11064kb

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: 9ms
memory: 10436kb

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: 9ms
memory: 11112kb

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: 6ms
memory: 11892kb

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: 8ms
memory: 11132kb

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: -25
Wrong Answer
time: 9ms
memory: 10408kb

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:

-8446743988948961169

result:

wrong answer 1st lines differ - expected: '70750757930', found: '-8446743988948961169'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%