QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#749586 | #9540. Double 11 | hos_lyric | WA | 0ms | 3984kb | C++14 | 3.3kb | 2024-11-15 05:24:51 | 2024-11-15 05:24:52 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
template <class T, class Cost> struct MonotoneMinDP {
int n;
Cost cost;
vector<T> ts;
vector<int> par;
MonotoneMinDP() {}
MonotoneMinDP(int n_, Cost cost_) : n(n_), cost(cost_) {
ts.assign(n + 1, T());
par.assign(n + 1, -1);
update(0, n);
rec(0, n);
}
void update(int l, int r) {
const T t = ts[l] + cost(l, r);
if (!~par[r] || ts[r] > t) {
ts[r] = t;
par[r] = l;
}
}
// precondition: ts[0, l] is determined
// precondition: transitions from [0, l] to r is checked
// postcondition: ts[0, r] is determined
void rec(int l, int r) {
if (r - l <= 1) return;
const int m = (l + r) / 2;
for (int i = max(par[l], 0); i <= max(par[r], 0); ++i) update(i, m);
rec(l, m);
for (int i = l + 1; i <= m; ++i) update(i, r);
rec(m, r);
}
};
template <class T, class Cost> MonotoneMinDP<T, Cost> monotoneMinDP(int n, Cost cost) {
return MonotoneMinDP<T, Cost>(n, cost);
}
template <class D, class F> auto goldenMax(D a, D b, int numIters, F f) {
constexpr D GOLD = (3.0L - sqrt(5.0L)) / 2.0L;
D c = a + GOLD * (b - a), d = b - GOLD * (b - a);
auto fc = f(c), fd = f(d);
for (int iter = 0; iter < numIters; ++iter) {
if (fc < fd) { a = c; c = d; d = b - GOLD * (b - a); fc = fd; fd = f(d); }
else { b = d; d = c; c = a + GOLD * (b - a); fd = fc; fc = f(c); }
}
return make_pair(f(c), c);
}
using Double = long double;
int N, M;
vector<Int> S;
int main() {
for (; ~scanf("%d%d", &N, &M); ) {
S.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lld", &S[i]);
}
sort(S.begin(), S.end());
vector<Int> SSum(N + 1, 0);
for (int i = 0; i < N; ++i) {
SSum[i + 1] = SSum[i] + S[i];
}
const auto res = goldenMax(-1e15L, +1e15L, 200, [&](const Double pena) -> Double {
return monotoneMinDP<Double>(N, [&](int l, int r) -> Double {
return sqrt((Double)((r - l) * (SSum[r] - SSum[l]))) + pena;
}).ts[N] - M * pena;
});
printf("%.20Lf\n", res.first);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3984kb
input:
4 2 1 2 3 4
output:
6.19114712955711948362
result:
ok found '6.191147130', expected '6.191147130', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
10 3 1 2 3 4 5 6 7 8 9 10
output:
22.59162536651412858668
result:
ok found '22.591625367', expected '22.591625367', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
1 1 1
output:
1.00000000000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3864kb
input:
1 1 100000
output:
316.22776794433593750000
result:
wrong answer 1st numbers differ - expected: '316.2277660', found: '316.2277679', error = '0.0000000'