QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712664 | #9581. 都市叠高 | fsy_juruo | WA | 110ms | 320396kb | C++17 | 967b | 2024-11-05 16:35:31 | 2024-11-05 16:35:31 |
Judging History
answer
#include <bits/stdc++.h>
using LL = long long;
const int maxN = 5e3 + 5;
int n;
int x[maxN], y[maxN];
double f[maxN];
LL dis[maxN][maxN], max_dist[maxN][maxN];
int main() {
std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
std::cin >> n;
for(int i = 1; i <= n; i++) {
std::cin >> x[i] >> y[i];
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
dis[i][j] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}
}
for(int j = 1; j <= n; j++) {
for(int i = j; i >= 1; i--) {
dis[i][j] = std::max(dis[i][j], dis[i + 1][j]);
}
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
max_dist[i][j] = std::max(max_dist[i][j - 1], dis[i][j]);
}
}
f[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = i; j >= 1; j--) f[i] = std::max(f[i], f[j - 1] + sqrt(max_dist[j][i]));
}
std::cout << std::fixed << std::setprecision(15) << f[n] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5740kb
input:
7 1 0 0 1 0 0 1 1 1 2 3 2 3 3
output:
5.656854249492380
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 320396kb
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...
output:
64388790.216936096549034
result:
wrong answer 1st numbers differ - expected: '2798587991989.8847656', found: '64388790.2169361', error = '0.9999770'