QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#702760 | #9540. Double 11 | ucup-team987# | TL | 4027ms | 6612kb | C++23 | 11.9kb | 2024-11-02 16:31:59 | 2024-11-02 16:32:13 |
Judging History
answer
/**
* date : 2024-11-02 17:31:52
* author : Nyaan
*/
#define NDEBUG
using namespace std;
// intrinstic
#include <immintrin.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tr2/dynamic_bitset>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// utility
namespace Nyaan {
using ll = long long;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
using vi = vector<int>;
using vl = vector<long long>;
using vd = V<double>;
using vs = V<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T, typename U>
struct P : pair<T, U> {
template <typename... Args>
constexpr P(Args... args) : pair<T, U>(args...) {}
using pair<T, U>::first;
using pair<T, U>::second;
P &operator+=(const P &r) {
first += r.first;
second += r.second;
return *this;
}
P &operator-=(const P &r) {
first -= r.first;
second -= r.second;
return *this;
}
P &operator*=(const P &r) {
first *= r.first;
second *= r.second;
return *this;
}
template <typename S>
P &operator*=(const S &r) {
first *= r, second *= r;
return *this;
}
P operator+(const P &r) const { return P(*this) += r; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator*(const P &r) const { return P(*this) *= r; }
template <typename S>
P operator*(const S &r) const {
return P(*this) *= r;
}
P operator-() const { return P{-first, -second}; }
};
using pl = P<ll, ll>;
using pi = P<int, int>;
using vp = V<pl>;
constexpr int inf = 1001001001;
constexpr long long infLL = 4004004004004004004LL;
template <typename T>
int sz(const T &t) {
return t.size();
}
template <typename T, typename U>
inline bool amin(T &x, U y) {
return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
return (x < y) ? (x = y, true) : false;
}
template <typename T>
inline T Max(const vector<T> &v) {
return *max_element(begin(v), end(v));
}
template <typename T>
inline T Min(const vector<T> &v) {
return *min_element(begin(v), end(v));
}
template <typename T>
inline long long Sum(const vector<T> &v) {
return accumulate(begin(v), end(v), 0LL);
}
template <typename T>
int lb(const vector<T> &v, const T &a) {
return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
return upper_bound(begin(v), end(v), a) - begin(v);
}
constexpr long long TEN(int n) {
long long ret = 1, x = 10;
for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);
return ret;
}
template <typename T, typename U>
pair<T, U> mkp(const T &t, const U &u) {
return make_pair(t, u);
}
template <typename T>
vector<T> mkrui(const vector<T> &v, bool rev = false) {
vector<T> ret(v.size() + 1);
if (rev) {
for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];
} else {
for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
}
return ret;
};
template <typename T>
vector<T> mkuni(const vector<T> &v) {
vector<T> ret(v);
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
template <typename F>
vector<int> mkord(int N, F f) {
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), f);
return ord;
}
template <typename T>
vector<int> mkinv(vector<T> &v) {
int max_val = *max_element(begin(v), end(v));
vector<int> inv(max_val + 1, -1);
for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
return inv;
}
vector<int> mkiota(int n) {
vector<int> ret(n);
iota(begin(ret), end(ret), 0);
return ret;
}
template <typename T>
T mkrev(const T &v) {
T w{v};
reverse(begin(w), end(w));
return w;
}
template <typename T>
bool nxp(T &v) {
return next_permutation(begin(v), end(v));
}
// 返り値の型は入力の T に依存
// i 要素目 : [0, a[i])
template <typename T>
vector<vector<T>> product(const vector<T> &a) {
vector<vector<T>> ret;
vector<T> v;
auto dfs = [&](auto rc, int i) -> void {
if (i == (int)a.size()) {
ret.push_back(v);
return;
}
for (int j = 0; j < a[i]; j++) v.push_back(j), rc(rc, i + 1), v.pop_back();
};
dfs(dfs, 0);
return ret;
}
// F : function(void(T&)), mod を取る操作
// T : 整数型のときはオーバーフローに注意する
template <typename T>
T Power(T a, long long n, const T &I, const function<void(T &)> &f) {
T res = I;
for (; n; f(a = a * a), n >>= 1) {
if (n & 1) f(res = res * a);
}
return res;
}
// T : 整数型のときはオーバーフローに注意する
template <typename T>
T Power(T a, long long n, const T &I = T{1}) {
return Power(a, n, I, function<void(T &)>{[](T &) -> void {}});
}
template <typename T>
T Rev(const T &v) {
T res = v;
reverse(begin(res), end(res));
return res;
}
template <typename T>
vector<T> Transpose(const vector<T> &v) {
using U = typename T::value_type;
if(v.empty()) return {};
int H = v.size(), W = v[0].size();
vector res(W, T(H, U{}));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
res[j][i] = v[i][j];
}
}
return res;
}
template <typename T>
vector<T> Rotate(const vector<T> &v, int clockwise = true) {
using U = typename T::value_type;
int H = v.size(), W = v[0].size();
vector res(W, T(H, U{}));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (clockwise) {
res[W - 1 - j][i] = v[i][j];
} else {
res[j][H - 1 - i] = v[i][j];
}
}
}
return res;
}
} // namespace Nyaan
// bit operation
namespace Nyaan {
__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {
return __builtin_popcountll(a);
}
inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }
template <typename T>
inline int gbit(const T &a, int i) {
return (a >> i) & 1;
}
template <typename T>
inline void sbit(T &a, int i, bool b) {
if (gbit(a, i) != b) a ^= T(1) << i;
}
constexpr long long PW(int n) { return 1LL << n; }
constexpr long long MSK(int n) { return (1LL << n) - 1; }
} // namespace Nyaan
// inout
namespace Nyaan {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
istream &operator>>(istream &is, __int128_t &x) {
string S;
is >> S;
x = 0;
int flag = 0;
for (auto &c : S) {
if (c == '-') {
flag = true;
continue;
}
x *= 10;
x += c - '0';
}
if (flag) x = -x;
return is;
}
istream &operator>>(istream &is, __uint128_t &x) {
string S;
is >> S;
x = 0;
for (auto &c : S) {
x *= 10;
x += c - '0';
}
return is;
}
ostream &operator<<(ostream &os, __int128_t x) {
if (x == 0) return os << 0;
if (x < 0) os << '-', x = -x;
string S;
while (x) S.push_back('0' + x % 10), x /= 10;
reverse(begin(S), end(S));
return os << S;
}
ostream &operator<<(ostream &os, __uint128_t x) {
if (x == 0) return os << 0;
string S;
while (x) S.push_back('0' + x % 10), x /= 10;
reverse(begin(S), end(S));
return os << S;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
struct IoSetupNya {
IoSetupNya() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetupnya;
} // namespace Nyaan
// debug
#ifdef NyaanDebug
#define trc(...) (void(0))
#endif
#ifndef NyaanDebug
#define trc(...) (void(0))
#endif
#ifndef NyaanLocal
#define trc2(...) (void(0))
#endif
// macro
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define die(...) \
do { \
Nyaan::out(__VA_ARGS__); \
return; \
} while (0)
namespace Nyaan {
void solve();
}
int main() { Nyaan::solve(); }
//
template <typename T>
vector<T> monge_shortest_path(int N, const function<T(int, int)>& f) {
T INF = 1e100;
vector<T> dp(N + 1, INF);
vector<int> x(N + 1, 0);
auto check = [&](int from, int to) {
if (from >= to) return;
T cost = f(from, to);
if (dp[from] + cost < dp[to]) dp[to] = dp[from] + cost, x[to] = from;
};
auto dfs = [&](auto rc, int l, int r) -> void {
if (l + 1 >= r) return;
int m = (l + r) / 2;
for (int i = x[l]; i <= x[r]; i++) check(i, m);
rc(rc, l, m);
for (int i = l + 1; i <= m; i++) check(i, r);
rc(rc, m, r);
};
dp[0] = 0, check(0, N), dfs(dfs, 0, N);
return dp;
}
using namespace Nyaan;
void q() {
inl(N, D);
vl A(N);
in(A);
sort(all(A));
vl R = mkrui(A);
using T = long double;
auto f = [&](int l, int r) -> long double {
return sqrtl((R[r] - R[l]) * (r - l));
};
auto dp = [&](long double x) -> T {
auto g = [&](int from, int to) -> T { return f(from, to) + x; };
T cost = monge_shortest_path<T>(N, g)[N];
return cost - T{1} * D * x;
};
long double l = 0, r = 2e8;
rep(_, 200) {
long double llr = (l + l + r) / 3;
long double lrr = (l + r + r) / 3;
if (dp(llr) < dp(lrr)) {
l = llr;
} else {
r = lrr;
}
}
trc(l, r);
out(dp((l + r) / 2));
}
void Nyaan::solve() {
int t = 1;
// in(t);
while (t--) q();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3932kb
input:
4 2 1 2 3 4
output:
6.191147129557119
result:
ok found '6.191147130', expected '6.191147130', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
10 3 1 2 3 4 5 6 7 8 9 10
output:
22.591625366514129
result:
ok found '22.591625367', expected '22.591625367', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
1 1 1
output:
1.000000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 1 100000
output:
316.227766016840178
result:
ok found '316.227766017', expected '316.227766017', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
7 1 10 47 53 9 83 33 15
output:
41.833001326704107
result:
ok found '41.833001327', expected '41.833001327', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
8 5 138 1702 119 1931 418 1170 840 1794
output:
233.901654551943584
result:
ok found '233.901654552', expected '233.901654552', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
58 1 888 251 792 847 685 3 182 461 102 348 555 956 771 901 712 878 580 631 342 333 285 899 525 725 537 718 929 653 84 788 104 355 624 803 253 853 201 995 536 184 65 205 540 652 549 777 248 405 677 950 431 580 600 846 328 429 134 983
output:
1355.265287683560018
result:
ok found '1355.265287684', expected '1355.265287684', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
88 30 67117 31903 93080 85196 16438 97116 11907 72959 83651 41273 52873 81892 81468 51323 99992 58869 54258 7183 87358 90990 80596 41252 90769 82705 61434 8524 13575 10787 53950 96768 12062 34637 27806 70937 69653 28380 90236 3352 27537 3873 91006 89790 25369 91825 82734 5588 4539 74118 47098 84741 ...
output:
18791.475354094100112
result:
ok found '18791.475354094', expected '18791.475354094', error '0.000000000'
Test #9:
score: 0
Accepted
time: 29ms
memory: 3952kb
input:
987 59 5209 1618 7129 7700 893 6647 8231 3314 9844 1347 6789 2711 3968 7416 5864 9190 9564 8874 7357 2087 530 8754 7935 6772 3475 8206 2898 2717 9252 8686 6604 5188 7451 9977 9366 7618 6294 6454 3919 3232 8164 8403 8617 2191 5257 626 8554 1952 1727 4759 205 9453 3312 9387 4798 7774 7005 8892 3570 50...
output:
66075.508587054646860
result:
ok found '66075.508587055', expected '66075.508587055', error '0.000000000'
Test #10:
score: 0
Accepted
time: 13ms
memory: 3876kb
input:
572 529 48392 84311 16267 29255 52276 20511 75195 95522 64489 52229 74478 69766 41777 25148 59976 66512 62953 16779 69312 98832 96131 94700 46403 58028 12868 83503 80367 51036 63398 7509 55193 76715 29143 75925 89863 89244 5561 21242 9047 89763 78016 86274 11382 88520 72343 29729 70986 86600 43707 7...
output:
119849.322681758061073
result:
ok found '119849.322681758', expected '119849.322681758', error '0.000000000'
Test #11:
score: 0
Accepted
time: 211ms
memory: 3920kb
input:
6133 2231 2292 4026 3420 3246 5243 41 4223 468 682 5008 1497 584 1573 7049 5848 4129 5555 9957 9311 7225 6065 9498 3569 1695 717 1968 9690 7557 8700 9427 5142 371 8788 2260 9576 2674 4322 7448 5829 9123 982 7591 438 1590 9459 5982 5002 243 4144 4254 9585 9988 6745 3691 9602 2297 9518 1181 9814 1746 ...
output:
406852.366900471620824
result:
ok found '406852.366900472', expected '406852.366900471', error '0.000000000'
Test #12:
score: 0
Accepted
time: 282ms
memory: 4124kb
input:
8384 5123 19058 18998 87373 34122 75328 47694 7628 72373 15038 82392 99284 70202 49919 24589 3369 42325 8281 56682 20694 78018 67433 34318 26086 37124 18668 94430 78732 53794 58279 21730 60156 95172 58849 10021 70991 26522 88420 92248 63779 33077 16703 80111 94041 85804 3110 21282 12757 69593 53872 ...
output:
1764954.761128672619407
result:
ok found '1764954.761128673', expected '1764954.761128677', error '0.000000000'
Test #13:
score: 0
Accepted
time: 4027ms
memory: 6612kb
input:
92842 83212 71466 9482 98728 78471 22915 2470 5999 53211 25994 3996 11349 30511 56448 17277 78308 18316 42069 38636 63127 26256 63985 57249 58305 64366 17839 28518 18980 95945 36316 6076 69530 96509 6940 6039 56048 41847 82118 41054 49670 95896 45891 74636 90736 75413 27251 87730 68344 66202 71879 5...
output:
19558873.688870169966322
result:
ok found '19558873.688870169', expected '19558873.688863300', error '0.000000000'
Test #14:
score: -100
Time Limit Exceeded
input:
93773 73078 12212 18977 10701 17909 16643 1406 15608 19767 11321 4708 10418 5834 10141 18240 12668 2694 11528 16150 8201 793 9736 15133 17474 6052 830 8574 1473 6393 11680 9784 16406 3428 10520 6431 7941 3167 17474 16569 19046 9595 7858 12512 7204 414 13548 7490 9887 9184 4298 1124 8330 749 12122 14...