QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712664#9581. 都市叠高fsy_juruoWA 110ms320396kbC++17967b2024-11-05 16:35:312024-11-05 16:35:31

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 16:35:31]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:320396kb
  • [2024-11-05 16:35:31]
  • 提交

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'