QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #770408 | #9581. 都市叠高 | renew | TL | 237ms | 207036kb | Python3 | 627b | 2024-11-21 21:43:24 | 2024-11-21 21:43:29 |
Judging History
answer
import math
N = 5005
n = int(input())
x = [0] * N
y = [0] * N
dp = [[0.0] * N for _ in range(N)]
ndp = [0.0] * N
for i in range(1, n + 1):
x[i], y[i] = map(int, input().split())
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
dp[i][j] = math.hypot(x[i] - x[j], y[i] - y[j])
for length in range(3, n + 1):
for l in range(1, n - length + 2):
r = l + length - 1
dp[l][r] = max(dp[l][r], dp[l + 1][r], dp[l][r - 1])
ndp[0] = 0.0
for i in range(1, n + 1):
for j in range(i):
ndp[i] = max(ndp[i], ndp[j] + dp[j + 1][i])
print(f"{ndp[n]:.10f}")
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 237ms
memory: 207036kb
input:
7 1 0 0 1 0 0 1 1 1 2 3 2 3 3
output:
5.6568542495
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: -100
Time Limit Exceeded
input:
4741 583042625 -288151442 901234470 -999760464 -974135773 -819820344 562644007 892707743 -120734580 -288167839 -14369253 88358276 -150949453 -39424771 -947214734 -826830020 578141361 443534304 -783950948 394211236 861595911 -751206580 570425640 624990919 484450011 -470115909 -417437663 22205205 -278...