QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#251831#7691. B Road Bandmendicillin2#Compile Error//C++172.2kb2023-11-15 10:09:152023-11-15 10:09:17

Judging History

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

  • [2023-11-15 10:09:17]
  • 评测
查看
  • [2023-11-15 10:09:15]
  • 提交

answer

debug
#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, 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);
		}
	}

	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;
			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;
			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, N+1, 0, N+1);
		swap(dp, ndp);
	}

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

	return 0;
}
源文件, 语言: C++17

详细 

answer.code:1:1: error: ‘debug’ does not name a type
    1 | debug
      | ^~~~~
In file included from /usr/include/c++/11/cmath:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/include/c++/11/ext/type_traits.h:162:35: error: ‘bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
  162 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/11/ext/type_traits.h:157:5: note: previous declaration ‘template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)’
  157 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/11/ext/type_traits.h:162:26: error: ‘nullptr_t’ is not a member of ‘std’
  162 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/include/c++/11/type_traits:405:26: error: ‘std::size_t’ has not been declared
  405 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/11/type_traits:406:25: error: ‘_Size’ was not declared in this scope
  406 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/11/type_traits:406:31: error: template argument 1 is invalid
  406 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/11/type_traits:511:42: error: ‘nullptr_t’ is not a member of ‘std’
  511 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
/usr/include/c++/11/type_traits:511:51: error: template argument 1 is invalid
  511 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                                   ^
/usr/include/c++/11/type_traits:1311:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
 1311 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/lib/gcc/x86_64-linux-gnu/11/include/stddef.h:209:23: note: ‘size_t’ declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/include/c++/11/type_traits:1311:57: error: template argument 1 is invalid
 1311 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/11/type_traits:1311:57: note: invalid template non-type parameter
/usr/include/c++/11/type_traits:1320:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
 1320 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/lib/gcc/x86_64-linux-gnu/11/include/stddef.h:209:23: note: ‘size_t’ declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/include/c++/11/type_traits:1320:46: error: template argument 1 is invalid
 1320 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/11/type_traits:1320:46: note: invalid template non-type parameter
/usr/include/c++/11/type_traits:1322:26: error: ‘std::size_t’ has not been declared
 1322 |   template<typename _Tp, std::size_t _S...
English 繁體中文 简体中文

服务器时间: 2024-12-05 09:17:24 | 开源项目