Submission #1777888
Source Code Expand
#include<iostream>
#include<iomanip>
#include"math.h"
int n, start, goal;
int l[200000], r[200000];
double dp[2][200000];
double rec(int x, int y, double num) {
double res = 1000000;
//ゴールへ(単数)
if (n - y <= 1)
res = num + sqrt((goal - x)*(goal - x) + 1);
//ゴールへ(複数)
for (int i = 1; i <= n - y - 1; i++)
if (l[y + i]>x + (double)(goal - x)*i / (n - y) || x + (double)(goal - x)*i / (n - y)>r[y + i])
goto flaga;
res = res<num + sqrt((goal - x)*(goal - x) + (n - y)*(n - y)) ? res : num + sqrt((goal - x)*(goal - x) + (n - y)*(n - y));
flaga:
//一つ次
if (y<n-1) {
res =
res<rec(l[y + 1], y + 1, num + sqrt((l[y + 1] - x)*(l[y + 1] - x) + 1)) ?
res : rec(l[y + 1], y + 1, num + sqrt((l[y + 1] - x)*(l[y + 1] - x) + 1));
res =
res<rec(r[y + 1], y + 1, num + sqrt((r[y + 1] - x)*(r[y + 1] - x) + 1)) ?
res : rec(r[y + 1], y + 1, num + sqrt((r[y + 1] - x)*(r[y + 1] - x) + 1));
}
//複数次
for (int i = 2; i <= n - y; i++) {
for (int j = 1; j <= i - 1; j++) {
if (l[y + j]>x + (double)(l[y + i] - x)*j / i || x + (double)(l[y + i] - x)*j / i>r[y + j])
goto flagb;
}
res = res<rec(l[y + i], y + i, num + sqrt((l[y + i] - x)*(l[y + i] - x) + i*i)) ?
res : rec(l[y + i], y + i, num + sqrt((l[y + i] - x)*(l[y + i] - x) + i*i));
flagb:;
}
for (int i = 2; i <= n - y; i++) {
for (int j = 1; j <= i - 1; j++) {
if (l[y + j]>x + (double)(r[y + i] - x)*j / i || x + (double)(r[y + i] - x)*j / i>r[y + j])
goto flagc;
}
res = res<rec(r[y + i], y + i, num + sqrt((r[y + i] - x)*(r[y + i] - x) + i*i)) ?
res : rec(r[y + i], y + i, num + sqrt((r[y + i] - x)*(r[y + i] - x) + i*i));
flagc:;
}
return res;
}
int main() {
std::cin >> n >> start >> goal;
for (int i = 0; i<n + 1; i++)
std::cin >> l[i] >> r[i];
std::cout << std::setprecision(15)<<rec(start, 0, 0) << std::endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - レースゲーム |
User |
HPaddy |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1937 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
23680 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample1.txt, 00_sample2.txt, 01_rnd_large_00.txt, 01_rnd_large_01.txt, 01_rnd_large_02.txt, 01_rnd_small_00.txt, 01_rnd_small_01.txt, 01_rnd_small_02.txt, 02_narrowrnd_large_00.txt, 02_narrowrnd_large_01.txt, 02_narrowrnd_small_00.txt, 02_narrowrnd_small_01.txt, 03_zigzag_large_00.txt, 03_zigzag_small_00.txt, 04_middle_large_00.txt, 04_middle_large_01.txt, 04_middle_large_02.txt, 04_middle_small_00.txt, 04_middle_small_01.txt, 04_middle_small_02.txt, 05_turnleft_large_00.txt, 05_turnleft_small_00.txt, 06_turnright_large_00.txt, 06_turnright_small_00.txt, 07_free_large_00.txt, 07_free_small_00.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample1.txt |
AC |
2 ms |
2304 KB |
00_sample2.txt |
AC |
2 ms |
2304 KB |
01_rnd_large_00.txt |
TLE |
2104 ms |
21632 KB |
01_rnd_large_01.txt |
TLE |
2104 ms |
21632 KB |
01_rnd_large_02.txt |
TLE |
2104 ms |
23680 KB |
01_rnd_small_00.txt |
TLE |
2103 ms |
2432 KB |
01_rnd_small_01.txt |
TLE |
2103 ms |
2432 KB |
01_rnd_small_02.txt |
TLE |
2103 ms |
2432 KB |
02_narrowrnd_large_00.txt |
TLE |
2104 ms |
21632 KB |
02_narrowrnd_large_01.txt |
TLE |
2104 ms |
21632 KB |
02_narrowrnd_small_00.txt |
TLE |
2103 ms |
2432 KB |
02_narrowrnd_small_01.txt |
TLE |
2103 ms |
2432 KB |
03_zigzag_large_00.txt |
TLE |
2104 ms |
21632 KB |
03_zigzag_small_00.txt |
TLE |
2103 ms |
2432 KB |
04_middle_large_00.txt |
TLE |
2104 ms |
21632 KB |
04_middle_large_01.txt |
TLE |
2104 ms |
21632 KB |
04_middle_large_02.txt |
TLE |
2104 ms |
21632 KB |
04_middle_small_00.txt |
TLE |
2103 ms |
2432 KB |
04_middle_small_01.txt |
TLE |
2103 ms |
2432 KB |
04_middle_small_02.txt |
TLE |
2103 ms |
2432 KB |
05_turnleft_large_00.txt |
TLE |
2104 ms |
21632 KB |
05_turnleft_small_00.txt |
TLE |
2103 ms |
2432 KB |
06_turnright_large_00.txt |
TLE |
2104 ms |
21632 KB |
06_turnright_small_00.txt |
TLE |
2103 ms |
2432 KB |
07_free_large_00.txt |
TLE |
2103 ms |
3200 KB |
07_free_small_00.txt |
TLE |
2103 ms |
2432 KB |