QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#251837#7691. B Road Bandmendicillin2#AC ✓775ms34632kbC++172.2kb2023-11-15 10:23:142023-11-15 10:23:15

Judging History

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

  • [2023-11-15 10:23:15]
  • 评测
  • 测评结果:AC
  • 用时:775ms
  • 内存:34632kb
  • [2023-11-15 10:23:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;
template <class D, class F> D gss(D a, D b, F f, D e = EPS) {
	D r = (sqrt(5) - 1) / 2;
	D x1 = b - r * (b-a), x2 = a + r * (b-a);
	auto f1 = f(x1), f2 = f(x2);
	while (x2 - x1 > e) {
		if (f1 < f2) {
			b = x2, x2 = x1, f2 = f1;
			x1 = b - r * (b-a), f1 = f(x1);
		} else {
			a = x1, x1 = x2, f1 = f2;
			x2 = a + r * (b-a), f2 = f(x2);
		}
	}
	return a;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int M, N, K, S; cin >> M >> N >> K >> S;

	using D = double;

	vector<D> X;
	for (int i = 0; i < M+N; i++) {
		D x; cin >> x;
		X.push_back(x);
	}

	auto sq = [&](D a) -> D { return a * a; };

	sort(X.begin(), X.end());
	int L = int(X.size());
	assert(L == N+M);
	vector<D> pref(L+1);
	vector<D> spref(L+1);
	for (int i = 0; i < L; i++) {
		pref[i+1] = pref[i] + X[i];
		spref[i+1] = spref[i] + sq(X[i]);
	}

	auto get_cost_at = [&](int l, int r, D x) -> D {
		// (x - x_i)^2
		// x^2 - 2 x x_i + x_i^2
		return (r-l) * sq(x) - 2 * x * (pref[r] - pref[l]) + (spref[r] - spref[l]);
	};
	auto get_cost = [&](int l, int r) -> D {
		assert(0 <= l); assert(l <= r); assert(r <= L);
		D best = gss<D>(0, 1000, [&](D x) -> D {
			return get_cost_at(l, r, x);
		});
		return get_cost_at(l, r, best);
	};

	const D INF = 1e20;
	vector<vector<D>> cost(L+1, vector<D>(L+1, INF));
	for (int l = 0; l <= L; l++) {
		for (int r = l; r <= L; r++) {
			cost[l][r] = get_cost(l, r);
		}
	}

	//cerr << cost[0][3] << endl;

	vector<D> dp(L+1, INF);
	dp[0] = 0;
	for (int z = 0; z < K; z++) {
		vector<D> ndp(L+1);
		auto trans = [&](int i, int j) -> D {
			if (i > j) return INF;
			assert(0 <= i && i <= j && j <= L);
			return dp[i] + cost[i][j];
		};
		auto go = [&](auto self, int s, int e, int l, int r) -> void {
			if (s == e) return;
			int i = (s+e)/2;
			assert(0 <= i && i <= L);
			int b = l;
			D bv = trans(b, i);
			for (int k = l+1; k < r; k++) {
				D kv = trans(k, i);
				if (kv < bv) {
					b = k;
					bv = kv;
				}
			}
			ndp[i] = bv;
			self(self, s, i, l, b+1);
			self(self, i+1, e, b, r);
		};
		go(go, 0, L+1, 0, L+1);
		swap(dp, ndp);
	}

	D ans = dp.back();
	ans += L * sq(D(S)/2);
	cout << ans << '\n';

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3768kb

input:

4 4 2 3
0.5 1.0 3.0 3.5
1.0 2.5 3.0 3.5

output:

18.86666666666667069308

result:

ok found '18.86667', expected '18.86667', error '0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

9 9 3 2
1 2 3 5 6 7 9 10 11
1 2 3 5 6 7 9 10 11

output:

30.00000000000000000000

result:

ok found '30.00000', expected '30.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

9 9 2 2
1 2 3 5 6 7 9 10 11
1 2 3 5 6 7 9 10 11

output:

69.89999999999997726263

result:

ok found '69.90000', expected '69.90000', error '0.00000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

9 9 4 2
1 2 3 5 6 7 9 10 11
1 2 3 5 6 7 9 10 11

output:

27.00000000000000000000

result:

ok found '27.00000', expected '27.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 775ms
memory: 34632kb

input:

1000 1000 50 50
330.73 339.71 953.72 23.16 638.53 63.45 962.76 333.8 598.13 217.16 515.65 61.91 700.25 674.76 623.15 664.65 721.77 286.49 69.91 880.07 547.7 433.38 384.93 802.7 130.46 874.74 285.52 280.83 764.82 528.59 978.47 4.95 325.9 183.52 748.54 867.48 434.04 730.72 439.99 918.07 426.39 868.28 ...

output:

1308206.85983910271897912025

result:

ok found '1308206.85984', expected '1308206.85984', error '0.00000'

Test #6:

score: 0
Accepted
time: 774ms
memory: 34580kb

input:

1000 1000 100 50
105.67 449.24 806.29 311.9 769.96 429.75 615.75 129.89 341.97 740.16 810.73 230.26 544.63 99.66 232.57 733.62 741.15 707.48 364.11 223.4 961.2 997.79 885.57 389.15 529.83 615.18 377.93 919.18 999.44 653.69 817.85 774.44 173.74 744.18 721.5 422.42 866.58 585.33 717.53 122.96 511.1 70...

output:

1263688.57987001352012157440

result:

ok found '1263688.57987', expected '1263688.57987', error '0.00000'

Test #7:

score: 0
Accepted
time: 188ms
memory: 11092kb

input:

500 500 100 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7...

output:

156332.49999998885323293507

result:

ok found '156332.50000', expected '156332.50000', error '0.00000'

Test #8:

score: 0
Accepted
time: 186ms
memory: 11084kb

input:

500 500 1 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7.1...

output:

226037085.00000002980232238770

result:

ok found '226037085.00000', expected '226037085.00000', error '0.00000'

Test #9:

score: 0
Accepted
time: 190ms
memory: 11132kb

input:

500 500 2 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7.1...

output:

364582.50000000000000000000

result:

ok found '364582.50000', expected '364582.50000', error '0.00000'

Test #10:

score: 0
Accepted
time: 190ms
memory: 11068kb

input:

500 500 3 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7.1...

output:

286457.50000000000000000000

result:

ok found '286457.50000', expected '286457.50000', error '0.00000'

Test #11:

score: 0
Accepted
time: 308ms
memory: 15500kb

input:

250 1000 97 47
11.51 12.23 12.91 13.73 14.51 15.11 15.83 16.57 17.33 18.11 18.89 19.87 20.53 21.29 22.13 22.87 23.57 24.23 25.31 26.17 26.87 27.41 28.19 29.03 29.99 30.79 31.81 32.57 33.31 34.13 35.11 35.71 36.43 37.27 38.21 39.07 39.89 40.57 41.39 42.31 42.97 44.09 44.93 45.83 46.57 47.51 48.31 49....

output:

697092.85445965081453323364

result:

ok found '697092.85446', expected '697092.85446', error '0.00000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

1 1 1 50
0
0

output:

1250.00000000000000000000

result:

ok found '1250.00000', expected '1250.00000', error '0.00000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

1 1 1 50
0
1000

output:

501250.00000000000000000000

result:

ok found '501250.00000', expected '501250.00000', error '0.00000'

Test #14:

score: 0
Accepted
time: 193ms
memory: 11000kb

input:

1 1000 99 1
2
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

8703.88636363472687662579

result:

ok found '8703.88636', expected '8703.88636', error '0.00000'

Test #15:

score: 0
Accepted
time: 703ms
memory: 34632kb

input:

1000 1000 100 10
0.0 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008 0.009 0.01 0.011 0.012 0.013 0.014 0.015 0.016 0.017 0.018 0.019 0.02 0.021 0.022 0.023 0.024 0.025 0.026 0.027 0.028 0.029 0.03 0.031 0.032 0.033 0.034 0.035 0.036 0.037 0.038 0.039 0.04 0.041 0.042 0.043 0.044 0.045 0.046 0.047 0...

output:

50000.06650066342990612611

result:

ok found '50000.06650', expected '50000.06650', error '0.00000'

Test #16:

score: 0
Accepted
time: 367ms
memory: 17876kb

input:

832 534 62 22
757.493 969.1209 924.3885 464.8884 703.9059 5.3945 28.0153 826.2629 51.3272 956.5959 109.8332 280.5574 360.0078 748.5931 178.8053 292.964 869.1198 227.3777 802.1165 451.8061 703.6826 355.7579 216.5385 539.5439 91.4301 829.2405 875.1581 704.5212 536.3218 347.2829 266.4107 225.4323 583.8...

output:

190260.87420294035109691322

result:

ok found '190260.87420', expected '190260.87420', error '0.00000'

Test #17:

score: 0
Accepted
time: 271ms
memory: 13988kb

input:

699 467 96 45
913.2083 450.4552 735.5268 27.7049 936.9643 963.2617 630.9603 749.6636 920.6194 69.1402 927.4449 403.6279 979.213 725.9698 8.0531 2.415 159.4208 773.2526 151.8 88.8923 746.5293 901.682 728.7017 508.776 905.6727 188.032 187.993 963.3742 402.6472 696.0754 811.9219 105.8354 971.0376 269.0...

output:

598119.35302348388358950615

result:

ok found '598119.35302', expected '598119.35302', error '0.00000'

Test #18:

score: 0
Accepted
time: 267ms
memory: 14256kb

input:

467 707 50 31
922.4672 288.2115 248.6613 787.4892 215.0621 138.2471 291.2981 442.6152 663.4357 286.3617 422.5612 741.0062 6.0355 738.8899 439.7847 141.3104 120.9414 108.6917 24.824 476.9891 654.4894 816.6031 442.9343 707.6849 694.5703 172.9833 584.9788 716.2458 522.2092 75.4161 894.5203 60.0289 612....

output:

315183.91535101196495816112

result:

ok found '315183.91535', expected '315183.91535', error '0.00000'

Test #19:

score: 0
Accepted
time: 214ms
memory: 11524kb

input:

953 78 97 22
548.6809 702.1484 728.3296 784.9799 430.9431 930.6424 875.6313 227.0124 83.7347 518.7594 76.0558 816.2232 916.794 674.5125 413.0768 585.3728 715.4719 549.0397 643.2298 91.5907 682.7935 643.5181 210.6304 334.4067 30.4261 132.0014 71.1378 951.1012 228.7686 47.841 105.6795 651.8146 526.491...

output:

131378.37040021334541961551

result:

ok found '131378.37040', expected '131378.37022', error '0.00000'

Test #20:

score: 0
Accepted
time: 13ms
memory: 3976kb

input:

115 164 63 46
421.7146 649.9187 175.9689 688.7938 891.7511 588.2231 234.7759 10.0299 482.8945 552.7068 295.576 437.7695 11.3659 621.4309 57.5582 131.3717 468.3941 39.8718 80.3117 901.6784 903.2252 269.0753 917.3674 184.9596 595.727 637.8203 8.0889 207.0107 153.1284 38.9418 323.2908 975.4139 605.7919...

output:

150458.99427486120839603245

result:

ok found '150458.99427', expected '150458.99427', error '0.00000'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

2 3 3 1
1 3
2 5 6

output:

2.25000000000000000000

result:

ok found '2.25000', expected '2.25000', error '0.00000'