#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
int N;
LL T,U[3001],V[3001],D[3001],E[3001];
LL solve(int,int);
LL dp1[3001][3001];
LL wa1(int now, int ret){
if(ret >= N) return (1LL)<<40;
if(dp1[now][ret] != -1) return dp1[now][ret];
return dp1[now][ret] = min(solve(now+1, ret+1), wa1(now,ret+1)) + D[now]+V[now] + T*2;
}
LL dp2[3001][3001];
LL wa2(int now, int ret){
if(ret <= 0) return (1LL)<<40;
if(dp2[now][ret] != -1) return dp2[now][ret];
return dp2[now][ret] = min(solve(now+1, ret-1), wa2(now,ret-1)) + U[now]+E[now] - T*2;
}
LL dp[3001][3001];
LL solve(int now, int ret){
if(now == 0) return dp[0][0] = solve(1, 0) + T;
if(now == N+1){
if(ret == 0) return 0;
else return (1LL)<<40;
}
if(dp[now][ret] != -1) return dp[now][ret];
LL re = LLONG_MAX;
//上りの最中
re = min(re, solve(now+1, ret) + U[now] + V[now] + T*ret*2 + T);
//下りの最中
if(ret > 0) re = min(re, solve(now+1, ret) + D[now] + E[now] + T*ret*2 + T);
//後で返ってくる
re = min(re, wa1(now, ret)+T*ret*2+T);
//折り返す
re = min(re, wa2(now, ret)+T*ret*2+T);
return dp[now][ret] = re;
}
int main(){
cin >> N >> T;
for(int i=0; i<N; i++) cin >> U[i+1] >> V[i+1] >> D[i+1] >> E[i+1];
for(int i=0; i<=N; i++){
for(int j=0; j<=N; j++){
dp[i][j] = -1;
dp1[i][j] = -1;
dp2[i][j] = -1;
}
}
cout << solve(0, 0) << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
560 KB |
Output is correct |
| 7 |
Correct |
3 ms |
512 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
512 KB |
Output is correct |
| 10 |
Correct |
3 ms |
556 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
2 ms |
556 KB |
Output is correct |
| 13 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1664 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1664 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 15 |
Correct |
26 ms |
1804 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
528 ms |
212264 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
516 ms |
212648 KB |
Output is correct |
| 4 |
Correct |
427 ms |
187520 KB |
Output is correct |
| 5 |
Correct |
327 ms |
155584 KB |
Output is correct |
| 6 |
Correct |
170 ms |
72412 KB |
Output is correct |
| 7 |
Correct |
81 ms |
45440 KB |
Output is correct |
| 8 |
Correct |
503 ms |
212332 KB |
Output is correct |
| 9 |
Correct |
536 ms |
212496 KB |
Output is correct |
| 10 |
Correct |
630 ms |
212468 KB |
Output is correct |
| 11 |
Correct |
489 ms |
212472 KB |
Output is correct |
| 12 |
Correct |
589 ms |
212600 KB |
Output is correct |
| 13 |
Correct |
478 ms |
212600 KB |
Output is correct |
| 14 |
Correct |
530 ms |
212516 KB |
Output is correct |
| 15 |
Correct |
539 ms |
212600 KB |
Output is correct |
| 16 |
Correct |
533 ms |
212500 KB |
Output is correct |
| 17 |
Correct |
570 ms |
212504 KB |
Output is correct |
