QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #251831 | #7691. B Road Band | mendicillin2# | Compile Error | / | / | C++17 | 2.2kb | 2023-11-15 10:09:15 | 2023-11-15 10:09:17 |
Judging History
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;
}
Details
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...