Submission #68293

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
template <class A> inline bool chmax(A &a, const A &b) { return b > a && (a = b, true); }
template <class A> inline bool chmin(A &a, const A &b) { return b < a && (a = b, true); }
template <class A> inline void chmod(A &a, const A b) { a = ((a%b)+b)%b; return; }
#define fi first
#define se second
#define ALL(a) (a).begin(),(a).end()
#define mp make_pair
double euqlid(int x, int y) {
return (sqrt(x*x+y*y));
}
int main() {
double dp[305][305], work;
int x0, x1, y0, y1;
cin >> x0 >> y0 >> x1 >> y1;
// 始点を左下にしたい
if (y0>y1) {
y0=301-y0;
y1=301-y1;
}
if (x0>x1) {
x0=301-x0;
x1=301-x1;
}
for (int i=0; i<=max(y0, y1); i++ ) {
for (int j=0; j<=max(x0, x1); j++ ) {
dp[i][j]=1e9;
}
}
// 始点と同じ軸上の点への最小コスト
for (int i=y0; i<=y1; i++ ) {
dp[i][x0]=i-y0;
}
for (int j=x0; j<=x1; j++ ) {
dp[y0][j]=j-x0;
}
// (i,j)から遷移する
for (int i=y0; i<=y1; i++ ) {
for (int j=x0; j<=x1; j++ ) {
chmin(dp[i+1][j], dp[i][j]+1);
chmin(dp[i][j+1], dp[i][j]+1);
chmin(dp[i+1][j+1], dp[i][j]+(i%2==0 && j%2==0 ? 2 : sqrt(2)));
if (i%2==1) {
// y=i+1の点へユークリッド辺を張る。
for (int k=j; k<x1; k++ ) {
chmin(dp[i+1][k+1], dp[i][j]+euqlid(k-j+1, 1));
}
}
if (j%2==1) {
// x=j+1の点へのユークリッド辺を張る。（yが同じ場合を含める）
for (int l=i; l<y1; l++ ) {
chmin(dp[l+1][j+1], dp[i][j]+euqlid(l-i+1, 1));
}
}
}
}
printf("%.8lf\n", dp[y1][x1]);
return 0;
}

ステータス

項目 データ
問題 1445 - 倉庫番ロボット
ユーザー名 ei1929
投稿日時 2021-09-05 15:10:55
言語 C++17
状態 Accepted
得点 10
ソースコード長 1771 Byte
最大実行時間 93 ms
最大メモリ使用量 1468 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 22 ms 600 KB
1
in2 AC 20 ms 612 KB
1
in3 AC 25 ms 708 KB
1
in4 AC 23 ms 716 KB
1
in5 AC 23 ms 548 KB
1
in6 AC 29 ms 620 KB
1
in7 AC 21 ms 696 KB
1
in8 AC 21 ms 644 KB
1
in9 AC 22 ms 728 KB
1
in10 AC 16 ms 688 KB
1
in11 AC 19 ms 648 KB
1
in12 AC 91 ms 1252 KB
1
in13 AC 84 ms 1144 KB
1
in14 AC 89 ms 1148 KB
1
in15 AC 85 ms 1292 KB
1
in16 AC 88 ms 1312 KB
1
in17 AC 80 ms 1196 KB
1
in18 AC 82 ms 1216 KB
1
in19 AC 86 ms 1232 KB
1
in20 AC 82 ms 1324 KB
1
in21 AC 88 ms 1340 KB
1
in22 AC 84 ms 1356 KB
1
in23 AC 79 ms 1244 KB
1
in24 AC 87 ms 1388 KB
1
in25 AC 90 ms 1404 KB
1
in26 AC 85 ms 1412 KB
1
in27 AC 84 ms 1304 KB
1
in28 AC 92 ms 1316 KB
1
in29 AC 85 ms 1328 KB
1
in30 AC 92 ms 1444 KB
1
in31 AC 90 ms 1328 KB
1
in32 AC 87 ms 1344 KB
1
in33 AC 90 ms 1364 KB
1
in34 AC 89 ms 1380 KB
1
in35 AC 93 ms 1268 KB
1
in36 AC 81 ms 1416 KB
1
in37 AC 92 ms 1300 KB
1
in38 AC 79 ms 1316 KB
1
in39 AC 82 ms 1332 KB
1
in40 AC 86 ms 1432 KB
1
in41 AC 87 ms 1444 KB
1
in42 AC 80 ms 1460 KB
1
in43 AC 88 ms 1352 KB
1
in44 AC 18 ms 736 KB
1
in45 AC 20 ms 1468 KB
1
in46 AC 30 ms 1356 KB
1
in47 AC 31 ms 1252 KB
1
in48 AC 23 ms 1408 KB
1