QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138426#366. Long Distance CoachRafi22#0 3ms10836kbC++141.7kb2023-08-11 18:16:022024-07-04 01:37:00

Judging History

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

  • [2024-07-04 01:37:00]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:10836kb
  • [2023-08-11 18:16:02]
  • 提交

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

Test #1:

score: 16
Accepted
time: 3ms
memory: 10684kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

score: 16
Accepted
time: 0ms
memory: 10096kb

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

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

input:

5 1 1 15 4
3
2 13

output:

43

result:

ok single line: '43'

Test #4:

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

input:

5 1 1 15 4
3
2 19

output:

45

result:

ok single line: '45'

Test #5:

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

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: 16
Accepted
time: 2ms
memory: 9240kb

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: 16
Accepted
time: 0ms
memory: 10836kb

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: 16
Accepted
time: 0ms
memory: 10244kb

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: 16
Accepted
time: 2ms
memory: 9624kb

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: 16
Accepted
time: 2ms
memory: 10268kb

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: 16
Accepted
time: 2ms
memory: 9448kb

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: 16
Accepted
time: 2ms
memory: 9636kb

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: 16
Accepted
time: 0ms
memory: 9628kb

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: 16
Accepted
time: 0ms
memory: 10588kb

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: 16
Accepted
time: 2ms
memory: 9608kb

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: 16
Accepted
time: 0ms
memory: 10560kb

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: 16
Accepted
time: 0ms
memory: 9464kb

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
Wrong Answer
time: 2ms
memory: 10816kb

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:

-5846744072754548886

result:

wrong answer 1st lines differ - expected: '15089', found: '-5846744072754548886'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%