QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#907614#8532. Train SchedulingMatutino100 ✓374ms396468kbC++172.6kb2025-02-20 16:01:262025-02-20 16:01:36

Judging History

This is the latest submission verdict.

  • [2025-02-20 16:01:36]
  • Judged
  • Verdict: 100
  • Time: 374ms
  • Memory: 396468kb
  • [2025-02-20 16:01:26]
  • Submitted

answer

#include<bits/stdc++.h>
#define reg register
#define int long long
inline int read(){
    reg int x=0,k=1; reg char ch=getchar();
    while ('0'>ch||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
    while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*k;
}
inline int min(reg int x,reg int y){return x<y?x:y;}
inline bool cmin(reg int &x,reg int y){return x>y?x=y,1:0;}
const int N=5010,INF=1e18;
int n,m,T,c[N],f[N][2],prea[N],preb[N],posa[N],posb[N],pos[N],tag[N][N][2];
std::vector<int> va,vb;
inline int geta(reg int l,reg int r,reg int x){return x*(r-l)-(prea[r]-prea[l]);}
inline int getb(reg int l,reg int r,reg int x){return x*(r-l)-(preb[r]-preb[l]);}
signed main(){
    n=read(),T=read();
    for (reg int i=1,x;i<=n;i++){
        char str[3];
        scanf("%s",str),x=read();
        if (str[0]=='A') va.push_back(x); else vb.push_back(x);
        c[++m]=x;
    }  
    va.push_back(0),vb.push_back(0);
    std::sort(c+1,c+m+1),m=std::unique(c+1,c+m+1)-c-1;
    std::sort(va.begin(),va.end()),std::sort(vb.begin(),vb.end());
    for (reg int i=1;i<va.size();i++) prea[i]=prea[i-1]+va[i];
    for (reg int i=1;i<vb.size();i++) preb[i]=preb[i-1]+vb[i];
    memset(tag,0x3f,sizeof(tag));
    reg int ans=INF,now=0;
    for (reg int i=1;i<=m;i++){
        reg int pa=0,pb=0,p=0; 
        memset(f,0x3f,sizeof(f));
        for (reg int j=0;j<=n+2;j++){
            while (pa+1<va.size()&&va[pa+1]<=c[i]+j*T) pa++;
            while (pb+1<vb.size()&&vb[pb+1]<=c[i]+j*T) pb++;
            while (p+1<=m&&c[p+1]<=c[i]+j*T) p++;
            posa[j]=pa,posb[j]=pb,pos[j]=p;
        }
        for (reg int j=0;j<vb.size();j++){
            cmin(tag[i][j][0],tag[i-1][j][0]);
            if (j<=posb[1]) cmin(f[0][0],tag[i][j][0]+getb(j,posb[1],c[i]+T));
        }
        for (reg int j=0;j<va.size();j++){
            cmin(tag[i][j][1],tag[i-1][j][1]);
            if (j<=posa[1]) cmin(f[0][1],tag[i][j][1]+geta(j,posa[1],c[i]+T));
        }
        for (reg int j=0;j<=n;j++){
            cmin(f[j][0],getb(0,posb[j+1],c[i]+(j+1)*T));
            cmin(f[j][1],geta(0,posa[j+1],c[i]+(j+1)*T));

            cmin(f[j+1][1],f[j][0]+geta(posa[j],posa[j+2],c[i]+(j+2)*T));
            cmin(f[j+1][0],f[j][1]+getb(posb[j],posb[j+2],c[i]+(j+2)*T));

            cmin(tag[pos[j+1]+1][posb[j]][0],f[j][1]);
            cmin(tag[pos[j+1]+1][posa[j]][1],f[j][0]);
            
            if (c[i]+j*T>=va.back()&&c[i]+(j+1)*T>=vb.back()) cmin(ans,f[j][0]);
            if (c[i]+j*T>=vb.back()&&c[i]+(j+1)*T>=va.back()) cmin(ans,f[j][1]);
        }
    }
    // std::cerr<<"<< "<<f[3][1][1]<<"\n";
    printf("%lld\n",ans);
    return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 4.16667
Accepted
time: 10ms
memory: 396200kb

input:

1 95
B 63

output:

0

result:

ok single line: '0'

Test #2:

score: 4.16667
Accepted
time: 23ms
memory: 396204kb

input:

4 1
B 3
B 2
A 1
A 3

output:

1

result:

ok single line: '1'

Test #3:

score: 4.16667
Accepted
time: 13ms
memory: 396204kb

input:

4 10
A 1
B 2
A 3
A 21

output:

13

result:

ok single line: '13'

Test #4:

score: 4.16667
Accepted
time: 12ms
memory: 396108kb

input:

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

output:

548047356974

result:

ok single line: '548047356974'

Test #5:

score: 4.16667
Accepted
time: 14ms
memory: 396104kb

input:

15 66666666666
B 18321553618
A 19075277868
B 23311375251
B 40808967822
A 1177192404
A 20959169967
A 55611055322
A 59819730757
A 4974902987
B 1222716560
A 16056478800
A 45716098074
A 50518537625
B 66538461856
B 66630582720

output:

542084726711

result:

ok single line: '542084726711'

Test #6:

score: 4.16667
Accepted
time: 7ms
memory: 396144kb

input:

15 66666666666
B 42940111219
B 60375044015
A 33037106266
B 56197221470
A 19061672260
A 20340458760
B 47889740766
A 29003368297
B 43165632313
B 31046123026
A 32586841316
B 42488614860
A 24994001232
A 43655072267
A 11263635180

output:

448149684862

result:

ok single line: '448149684862'

Test #7:

score: 4.16667
Accepted
time: 11ms
memory: 396120kb

input:

100 10000000000
B 176666666664
B 276666666637
A 526666666561
A 2679130135
B 496666666571
A 566666666552
B 696666666516
B 476666666580
B 876666666457
A 666666666529
B 656666666531
B 676666666524
A 2264099968
A 826666666472
B 376666666601
A 506666666568
B 396666666599
B 2241057559
A 386666666600
B 960...

output:

102978802857

result:

ok single line: '102978802857'

Test #8:

score: 4.16667
Accepted
time: 9ms
memory: 396128kb

input:

100 10000000000
A 246666666641
A 226666666649
B 976666666420
B 856666666457
A 406666666597
A 6737604411
A 346666666617
A 726666666491
B 176666666662
B 7630250095
B 616666666525
A 266666666635
B 316666666625
B 556666666544
B 576666666535
B 916666666438
B 256666666637
A 866666666455
A 766666666480
B 9...

output:

47936217526

result:

ok single line: '47936217526'

Test #9:

score: 4.16667
Accepted
time: 12ms
memory: 396168kb

input:

100 10000000000
B 896666666459
A 246666666646
A 566666666561
B 736666666508
B 536666666567
A 966666666444
B 376666666613
A 3462494580
A 406666666608
B 1909199404
A 506666666580
A 546666666563
A 886666666461
A 926666666455
A 5782193487
A 486666666584
A 6261863608
A 386666666612
B 436666666599
A 46666...

output:

80280002343

result:

ok single line: '80280002343'

Test #10:

score: 4.16667
Accepted
time: 12ms
memory: 396156kb

input:

100 10000000000
A 166666666666
A 406666666586
B 916666666419
B 356666666602
B 816666666449
A 4212009491
A 546666666530
B 736666666470
A 426666666576
B 836666666445
A 326666666612
A 866666666436
B 656666666487
B 996666666396
A 626666666499
A 486666666548
B 9091451701
B 556666666525
B 976666666402
B 6...

output:

94861796954

result:

ok single line: '94861796954'

Test #11:

score: 4.16667
Accepted
time: 19ms
memory: 396188kb

input:

500 2000000000
B 412666666318
A 510666666179
B 713348532
B 476666666236
A 422666666303
A 1607274852
B 184666666642
A 662666665958
A 166666666666
A 846666665664
A 838666665675
B 713588398
A 722666665879
A 558666666114
B 704666665904
A 702666665909
A 174666666659
B 568666666099
B 300666666478
A 145980...

output:

92916853209

result:

ok single line: '92916853209'

Test #12:

score: 4.16667
Accepted
time: 16ms
memory: 396044kb

input:

500 2000000000
A 934666665492
B 564666666056
B 788666665715
A 554666666072
A 838666665646
B 412666666271
A 490666666165
A 970666665440
A 818666665673
A 822666665664
B 484666666174
B 1969946218
B 1472123216
B 228666666559
B 1500232266
B 296666666461
A 902666665546
A 826666665659
A 394666666301
A 3066...

output:

106520016120

result:

ok single line: '106520016120'

Test #13:

score: 4.16667
Accepted
time: 20ms
memory: 396232kb

input:

500 2000000000
A 442666666243
B 776666665724
A 882666665557
B 1750350928
A 298666666462
A 922666665498
B 616666665977
B 319922261
B 300666666457
B 868666665581
A 434666666253
A 850666665609
B 725951487
A 186666666634
A 334666666400
B 804666665680
A 978666665418
A 786666665706
A 690666665867
A 902666...

output:

109798349797

result:

ok single line: '109798349797'

Test #14:

score: 4.16667
Accepted
time: 16ms
memory: 396188kb

input:

500 2000000000
A 186666666632
B 172666666657
A 834666665651
A 926666665517
B 460666666217
A 750666665772
B 1161674235
A 682666665869
A 982666665434
B 1126653769
B 280666666480
B 1455843431
A 454666666226
A 862666665607
B 212666666590
B 272666666494
A 602666665998
B 1322272380
A 394666666321
A 550666...

output:

98302806188

result:

ok single line: '98302806188'

Test #15:

score: 4.16667
Accepted
time: 63ms
memory: 396440kb

input:

2000 500000000
B 79262531
B 275384819
A 490666664677
A 429666665060
B 697166663371
A 675666663507
A 961666661825
B 192166666522
B 142528017
A 817666662677
A 948666661905
A 642666663730
B 787166662836
B 441166664999
B 691166663407
B 168166666654
A 543666664320
A 922666662058
B 481166664739
B 77116666...

output:

118403180255

result:

ok single line: '118403180255'

Test #16:

score: 4.16667
Accepted
time: 71ms
memory: 396184kb

input:

2000 500000000
A 419912922
A 693666663608
B 934166662183
B 803166662970
B 341514304
A 751666663282
A 890666662443
B 94436203
B 810166662937
B 824166662853
A 195666666495
A 621666663995
A 535666664515
A 471666664894
B 394567790
A 169666666647
A 614666664035
B 926166662230
B 113657574
B 949166662082
B...

output:

110143274947

result:

ok single line: '110143274947'

Test #17:

score: 4.16667
Accepted
time: 60ms
memory: 396288kb

input:

2000 500000000
A 953666661991
B 306166665846
B 350166665583
B 328166665714
A 474666664836
A 876666662430
B 738166663231
B 939166662074
A 520666664540
A 361666665513
B 228166666314
A 572666664248
A 731666663277
A 652666663752
A 582666664180
A 124599441
B 997166661746
B 654166663743
B 320166665758
A 4...

output:

110260437733

result:

ok single line: '110260437733'

Test #18:

score: 4.16667
Accepted
time: 58ms
memory: 396288kb

input:

2000 500000000
B 888166662375
A 886666662386
B 455166664999
A 417152040
A 873666662442
B 933166662112
B 230358294
B 636166663903
A 615666664036
B 573166664303
B 416539875
B 891166662356
B 224165899
A 274666666052
A 527666664582
A 746666663215
B 690166663583
A 64794015
B 692166663571
B 287166665979
B...

output:

104954387406

result:

ok single line: '104954387406'

Test #19:

score: 4.16667
Accepted
time: 354ms
memory: 396468kb

input:

5000 200000000
B 826866656733
A 173325862
B 363666663644
A 245066665434
A 776266657436
A 627866659663
A 189886330
A 813866656914
B 90406902
B 934466655162
B 302466664576
A 528666661191
A 342666663953
B 109905426
B 970466654654
A 813066656930
A 278266664945
B 443266662448
A 557066660758
B 21926666582...

output:

120788681412

result:

ok single line: '120788681412'

Test #20:

score: 4.16667
Accepted
time: 347ms
memory: 396392kb

input:

5000 200000000
A 699466658724
B 494866661817
A 919066655412
A 587866660431
A 931066655222
B 995666654285
A 852666656415
B 647266659521
B 809666657062
A 592266660369
B 782466657466
A 241866665547
B 777666657543
A 35772658
A 198666666170
A 488666661920
A 713866658484
B 302066664719
A 160065791
A 91786...

output:

123785707074

result:

ok single line: '123785707074'

Test #21:

score: 4.16667
Accepted
time: 354ms
memory: 396432kb

input:

5000 200000000
B 321666664353
B 209266666044
A 401066663196
A 867466656131
B 487266661889
A 707066658529
A 708035
B 152582349
B 661266659262
A 141581476
A 285866664916
B 281666664978
B 23631365
A 224266665822
A 581866660444
B 492066661816
A 178266666507
B 850066656394
A 462666662245
B 546466660997
B...

output:

121703249249

result:

ok single line: '121703249249'

Test #22:

score: 4.16667
Accepted
time: 355ms
memory: 396400kb

input:

5000 200000000
A 210266666001
A 893466655976
B 280066664954
B 736866658339
A 933066655355
B 678866659186
A 368266663673
B 820066657073
A 262266665214
A 180035408
B 24702218
A 406666663117
A 277866664991
B 173330642
A 313066664448
A 751866658117
B 883266656120
B 311666664467
B 34959515
B 194437123
A ...

output:

122179180601

result:

ok single line: '122179180601'

Test #23:

score: 4.16667
Accepted
time: 374ms
memory: 396404kb

input:

5000 200000000
B 632066659739
A 668666659192
B 976866654568
A 873466656076
A 275066665079
B 812066657011
B 28858966
A 188266666332
B 547666661034
A 283466664932
B 611666660051
B 990066654377
A 181466666427
B 458866662340
B 203666666099
A 783866657433
A 120205648
A 82300803
A 273466665103
B 682066658...

output:

122628842469

result:

ok single line: '122628842469'

Test #24:

score: 4.16667
Accepted
time: 361ms
memory: 396380kb

input:

5000 200000000
A 143756643
A 794666657257
A 527866661254
B 283266664899
A 729466658253
B 708466658556
A 64601713
B 33533125
B 402466663139
A 451866662401
A 756666657833
B 336866664093
A 340266664051
B 772066657587
B 529266661230
B 297666664674
A 935866655102
A 484266661891
B 998866654203
B 884866655...

output:

118906071812

result:

ok single line: '118906071812'