QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765472#8268. TychoPioneer#0 1ms5848kbC++201.4kb2024-11-20 14:23:222024-11-20 14:23:28

Judging History

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

  • [2024-11-20 14:23:28]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5848kb
  • [2024-11-20 14:23:22]
  • 提交

answer

#include <bits/stdc++.h>
 
#define ll long long
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
#define int ll

using namespace std;
 
const int MAX=1e5+10;
const int inf=2e18;
const int mod=1e9+7;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int b,p,d,n;
int dp[MAX][110],a[MAX];

void solve(){
    cin>>b>>p>>d>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    a[0]=0;
    for(int i=0;i<=n;i++)for(int j=0;j<p;j++)dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=0;i<=n;i++){
        for(int j=1;j<p;j++)dp[i][0]=min(dp[i][0],dp[i][j]+(p-j));
        for(int j=0;j<p;j++){
            int nxt=(j+(a[i+1]-a[i]))%p;
            int cnt=(a[i+1]-a[i]-1)/p;
            dp[i+1][nxt]=min(dp[i+1][nxt],dp[i][j]+cnt*d);
        }
    }
    int ans=inf;
    for(int i=0;i<=n;i++){
        int dist=b-a[i];
        ans=min(ans,dp[i][0]+((dist-1)/p)*d);
    }
    cout<<ans+b<<"\n";
}

signed main(){
    // freopen("escape.in","r",stdin);
    // freopen("escape.out","w",stdout);
    ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 0ms
memory: 3608kb

input:

1000000000000 1 1000000 0

output:

1000000999999000000

result:

ok single line: '1000000999999000000'

Test #2:

score: 8
Accepted
time: 1ms
memory: 5720kb

input:

100 10 11 10
10
11
20
30
38
49
50
60
70
90

output:

122

result:

ok single line: '122'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

100 10 11 15
1
5
9
15
24
25
39
40
45
66
75
79
85
95
97

output:

136

result:

wrong answer 1st lines differ - expected: '138', found: '136'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 5
Accepted
time: 0ms
memory: 3612kb

input:

108 100 10000 5
10
20
30
40
98

output:

110

result:

ok single line: '110'

Test #12:

score: 5
Accepted
time: 1ms
memory: 5848kb

input:

118 100 10000 5
10
20
30
98
108

output:

120

result:

ok single line: '120'

Test #13:

score: 5
Accepted
time: 1ms
memory: 5660kb

input:

206 100 10000 5
10
20
30
98
196

output:

210

result:

ok single line: '210'

Test #14:

score: 5
Accepted
time: 0ms
memory: 3608kb

input:

128 100 10000 5
10
20
98
108
118

output:

130

result:

ok single line: '130'

Test #15:

score: 5
Accepted
time: 0ms
memory: 3732kb

input:

206 100 10000 5
10
20
98
108
196

output:

210

result:

ok single line: '210'

Test #16:

score: 5
Accepted
time: 0ms
memory: 3660kb

input:

216 100 10000 5
10
20
98
196
206

output:

220

result:

ok single line: '220'

Test #17:

score: 5
Accepted
time: 1ms
memory: 5652kb

input:

304 100 10000 5
10
20
98
196
294

output:

310

result:

ok single line: '310'

Test #18:

score: 5
Accepted
time: 0ms
memory: 3620kb

input:

138 100 10000 5
10
98
108
118
128

output:

140

result:

ok single line: '140'

Test #19:

score: 5
Accepted
time: 1ms
memory: 5772kb

input:

206 100 10000 5
10
98
108
118
196

output:

210

result:

ok single line: '210'

Test #20:

score: 5
Accepted
time: 1ms
memory: 5712kb

input:

216 100 10000 5
10
98
108
196
206

output:

220

result:

ok single line: '220'

Test #21:

score: 5
Accepted
time: 0ms
memory: 3804kb

input:

304 100 10000 5
10
98
108
196
294

output:

310

result:

ok single line: '310'

Test #22:

score: 5
Accepted
time: 0ms
memory: 3732kb

input:

226 100 10000 5
10
98
196
206
216

output:

230

result:

ok single line: '230'

Test #23:

score: 5
Accepted
time: 0ms
memory: 3800kb

input:

304 100 10000 5
10
98
196
206
294

output:

310

result:

ok single line: '310'

Test #24:

score: 5
Accepted
time: 1ms
memory: 5700kb

input:

314 100 10000 5
10
98
196
294
304

output:

320

result:

ok single line: '320'

Test #25:

score: 5
Accepted
time: 0ms
memory: 3612kb

input:

402 100 10000 5
10
98
196
294
392

output:

410

result:

ok single line: '410'

Test #26:

score: 5
Accepted
time: 0ms
memory: 3804kb

input:

148 100 10000 5
98
108
118
128
138

output:

150

result:

ok single line: '150'

Test #27:

score: 5
Accepted
time: 0ms
memory: 5696kb

input:

206 100 10000 5
98
108
118
128
196

output:

210

result:

ok single line: '210'

Test #28:

score: 5
Accepted
time: 1ms
memory: 5844kb

input:

216 100 10000 5
98
108
118
196
206

output:

220

result:

ok single line: '220'

Test #29:

score: 5
Accepted
time: 0ms
memory: 3616kb

input:

304 100 10000 5
98
108
118
196
294

output:

310

result:

ok single line: '310'

Test #30:

score: 5
Accepted
time: 1ms
memory: 5776kb

input:

226 100 10000 5
98
108
196
206
216

output:

230

result:

ok single line: '230'

Test #31:

score: 5
Accepted
time: 0ms
memory: 3672kb

input:

304 100 10000 5
98
108
196
206
294

output:

310

result:

ok single line: '310'

Test #32:

score: 5
Accepted
time: 0ms
memory: 3732kb

input:

314 100 10000 5
98
108
196
294
304

output:

320

result:

ok single line: '320'

Test #33:

score: 5
Accepted
time: 0ms
memory: 3676kb

input:

402 100 10000 5
98
108
196
294
392

output:

410

result:

ok single line: '410'

Test #34:

score: 5
Accepted
time: 0ms
memory: 3672kb

input:

236 100 10000 5
98
196
206
216
226

output:

240

result:

ok single line: '240'

Test #35:

score: 5
Accepted
time: 0ms
memory: 3732kb

input:

304 100 10000 5
98
196
206
216
294

output:

310

result:

ok single line: '310'

Test #36:

score: 5
Accepted
time: 0ms
memory: 3656kb

input:

314 100 10000 5
98
196
206
294
304

output:

320

result:

ok single line: '320'

Test #37:

score: 5
Accepted
time: 0ms
memory: 3668kb

input:

402 100 10000 5
98
196
206
294
392

output:

410

result:

ok single line: '410'

Test #38:

score: 5
Accepted
time: 0ms
memory: 3676kb

input:

324 100 10000 5
98
196
294
304
314

output:

330

result:

ok single line: '330'

Test #39:

score: 5
Accepted
time: 0ms
memory: 3748kb

input:

402 100 10000 5
98
196
294
304
392

output:

410

result:

ok single line: '410'

Test #40:

score: 5
Accepted
time: 1ms
memory: 5640kb

input:

412 100 10000 5
98
196
294
392
402

output:

420

result:

ok single line: '420'

Test #41:

score: 5
Accepted
time: 0ms
memory: 3704kb

input:

500 100 10000 5
98
196
294
392
490

output:

510

result:

ok single line: '510'

Test #42:

score: 5
Accepted
time: 0ms
memory: 5840kb

input:

10 2 10 2
1
3

output:

41

result:

ok single line: '41'

Test #43:

score: 5
Accepted
time: 0ms
memory: 3604kb

input:

100 21 10 2
5
54

output:

140

result:

ok single line: '140'

Test #44:

score: 5
Accepted
time: 1ms
memory: 5796kb

input:

100 21 10 9
18
21
53
62
85
86
88
90
91

output:

121

result:

ok single line: '121'

Test #45:

score: 5
Accepted
time: 1ms
memory: 5772kb

input:

100 21 10 10
30
39
40
43
45
49
52
57
70
72

output:

132

result:

ok single line: '132'

Test #46:

score: 0
Wrong Answer
time: 1ms
memory: 5708kb

input:

156 20 1 10
19
37
54
70
85
99
112
124
135
145

output:

159

result:

wrong answer 1st lines differ - expected: '162', found: '159'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #109:

score: 15
Accepted
time: 0ms
memory: 3732kb

input:

1000000000000 1 1000000 0

output:

1000000999999000000

result:

ok single line: '1000000999999000000'

Test #110:

score: 15
Accepted
time: 0ms
memory: 3744kb

input:

108 100 10000 5
10
20
30
40
98

output:

110

result:

ok single line: '110'

Test #111:

score: 15
Accepted
time: 0ms
memory: 3804kb

input:

118 100 10000 5
10
20
30
98
108

output:

120

result:

ok single line: '120'

Test #112:

score: 15
Accepted
time: 0ms
memory: 3604kb

input:

206 100 10000 5
10
20
30
98
196

output:

210

result:

ok single line: '210'

Test #113:

score: 15
Accepted
time: 0ms
memory: 3676kb

input:

128 100 10000 5
10
20
98
108
118

output:

130

result:

ok single line: '130'

Test #114:

score: 15
Accepted
time: 1ms
memory: 5776kb

input:

206 100 10000 5
10
20
98
108
196

output:

210

result:

ok single line: '210'

Test #115:

score: 15
Accepted
time: 1ms
memory: 5648kb

input:

216 100 10000 5
10
20
98
196
206

output:

220

result:

ok single line: '220'

Test #116:

score: 15
Accepted
time: 0ms
memory: 3608kb

input:

304 100 10000 5
10
20
98
196
294

output:

310

result:

ok single line: '310'

Test #117:

score: 15
Accepted
time: 0ms
memory: 3668kb

input:

138 100 10000 5
10
98
108
118
128

output:

140

result:

ok single line: '140'

Test #118:

score: 15
Accepted
time: 0ms
memory: 3704kb

input:

206 100 10000 5
10
98
108
118
196

output:

210

result:

ok single line: '210'

Test #119:

score: 15
Accepted
time: 0ms
memory: 3656kb

input:

216 100 10000 5
10
98
108
196
206

output:

220

result:

ok single line: '220'

Test #120:

score: 15
Accepted
time: 1ms
memory: 5792kb

input:

304 100 10000 5
10
98
108
196
294

output:

310

result:

ok single line: '310'

Test #121:

score: 15
Accepted
time: 0ms
memory: 3676kb

input:

226 100 10000 5
10
98
196
206
216

output:

230

result:

ok single line: '230'

Test #122:

score: 15
Accepted
time: 1ms
memory: 5648kb

input:

304 100 10000 5
10
98
196
206
294

output:

310

result:

ok single line: '310'

Test #123:

score: 15
Accepted
time: 1ms
memory: 5696kb

input:

314 100 10000 5
10
98
196
294
304

output:

320

result:

ok single line: '320'

Test #124:

score: 15
Accepted
time: 1ms
memory: 5776kb

input:

402 100 10000 5
10
98
196
294
392

output:

410

result:

ok single line: '410'

Test #125:

score: 15
Accepted
time: 0ms
memory: 3752kb

input:

148 100 10000 5
98
108
118
128
138

output:

150

result:

ok single line: '150'

Test #126:

score: 15
Accepted
time: 0ms
memory: 3756kb

input:

206 100 10000 5
98
108
118
128
196

output:

210

result:

ok single line: '210'

Test #127:

score: 15
Accepted
time: 0ms
memory: 5792kb

input:

216 100 10000 5
98
108
118
196
206

output:

220

result:

ok single line: '220'

Test #128:

score: 15
Accepted
time: 0ms
memory: 3752kb

input:

304 100 10000 5
98
108
118
196
294

output:

310

result:

ok single line: '310'

Test #129:

score: 15
Accepted
time: 1ms
memory: 5708kb

input:

226 100 10000 5
98
108
196
206
216

output:

230

result:

ok single line: '230'

Test #130:

score: 15
Accepted
time: 0ms
memory: 3672kb

input:

304 100 10000 5
98
108
196
206
294

output:

310

result:

ok single line: '310'

Test #131:

score: 15
Accepted
time: 0ms
memory: 3800kb

input:

314 100 10000 5
98
108
196
294
304

output:

320

result:

ok single line: '320'

Test #132:

score: 15
Accepted
time: 0ms
memory: 3604kb

input:

402 100 10000 5
98
108
196
294
392

output:

410

result:

ok single line: '410'

Test #133:

score: 15
Accepted
time: 0ms
memory: 3656kb

input:

236 100 10000 5
98
196
206
216
226

output:

240

result:

ok single line: '240'

Test #134:

score: 15
Accepted
time: 0ms
memory: 3748kb

input:

304 100 10000 5
98
196
206
216
294

output:

310

result:

ok single line: '310'

Test #135:

score: 15
Accepted
time: 1ms
memory: 5796kb

input:

314 100 10000 5
98
196
206
294
304

output:

320

result:

ok single line: '320'

Test #136:

score: 15
Accepted
time: 1ms
memory: 5656kb

input:

402 100 10000 5
98
196
206
294
392

output:

410

result:

ok single line: '410'

Test #137:

score: 15
Accepted
time: 0ms
memory: 3644kb

input:

324 100 10000 5
98
196
294
304
314

output:

330

result:

ok single line: '330'

Test #138:

score: 15
Accepted
time: 1ms
memory: 5784kb

input:

402 100 10000 5
98
196
294
304
392

output:

410

result:

ok single line: '410'

Test #139:

score: 15
Accepted
time: 0ms
memory: 3736kb

input:

412 100 10000 5
98
196
294
392
402

output:

420

result:

ok single line: '420'

Test #140:

score: 15
Accepted
time: 1ms
memory: 5652kb

input:

500 100 10000 5
98
196
294
392
490

output:

510

result:

ok single line: '510'

Test #141:

score: 15
Accepted
time: 0ms
memory: 3672kb

input:

10 2 10 2
1
3

output:

41

result:

ok single line: '41'

Test #142:

score: 15
Accepted
time: 0ms
memory: 3808kb

input:

100 21 10 2
5
54

output:

140

result:

ok single line: '140'

Test #143:

score: 15
Accepted
time: 0ms
memory: 3740kb

input:

100 21 10 9
18
21
53
62
85
86
88
90
91

output:

121

result:

ok single line: '121'

Test #144:

score: 15
Accepted
time: 1ms
memory: 5716kb

input:

100 21 10 10
30
39
40
43
45
49
52
57
70
72

output:

132

result:

ok single line: '132'

Test #145:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

156 20 1 10
19
37
54
70
85
99
112
124
135
145

output:

159

result:

wrong answer 1st lines differ - expected: '162', found: '159'

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%