QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#609285 | #8524. Weather Forecast | Capps | WA | 0ms | 4020kb | C++20 | 5.1kb | 2024-10-04 11:46:54 | 2024-10-04 11:46:56 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
template <class T>
class FloatPointNumber {
static constexpr T EPS = 1e-12;
static_assert(EPS >= 0, "EPS < 0");
static constexpr int sgn(T x) {
if (x < -EPS) {
return -1;
} else {
return x > EPS;
}
}
static int precision;
static std::string inputStr;
T x;
public:
constexpr FloatPointNumber() : x{} {}
constexpr FloatPointNumber(T x) : x{x} {}
constexpr T val() const {
return x;
}
constexpr int sgn() const {
return sgn(x);
}
template <class G>
constexpr G round() const {
return G(x + 0.5);
}
static constexpr void setprecision(int len) {
precision = len;
}
// 四则运算
constexpr FloatPointNumber &operator+=(FloatPointNumber a) & {
x += a.x;
return *this;
}
friend constexpr FloatPointNumber operator+(FloatPointNumber a, FloatPointNumber b) {
return a += b;
}
constexpr FloatPointNumber operator-() const {
return FloatPointNumber(-x);
}
constexpr FloatPointNumber &operator-=(FloatPointNumber a) & {
x -= a.x;
return *this;
}
friend constexpr FloatPointNumber operator-(FloatPointNumber a, FloatPointNumber b) {
return a -= b;
}
constexpr FloatPointNumber &operator*=(FloatPointNumber a) & {
x *= a.x;
return *this;
}
friend constexpr FloatPointNumber operator*(FloatPointNumber a, FloatPointNumber b) {
return a *= b;
}
constexpr FloatPointNumber &operator/=(FloatPointNumber a) & {
x /= (long double)a.x;
return *this;
}
friend constexpr FloatPointNumber operator/(FloatPointNumber a, FloatPointNumber b) {
return a /= b;
}
// 比较运算
friend constexpr int operator<(FloatPointNumber a, FloatPointNumber b) {
return sgn(a.x - b.x) < 0;
}
friend constexpr int operator<=(FloatPointNumber a, FloatPointNumber b) {
return sgn(a.x - b.x) <= 0;
}
friend constexpr int operator>(FloatPointNumber a, FloatPointNumber b) {
return sgn(a.x - b.x) > 0;
}
friend constexpr int operator>=(FloatPointNumber a, FloatPointNumber b) {
return sgn(a.x - b.x) >= 0;
}
friend constexpr bool operator==(FloatPointNumber a, FloatPointNumber b) {
return sgn(a.x - b.x) == 0;
}
friend constexpr bool operator!=(FloatPointNumber a, FloatPointNumber b) {
return sgn(a.x - b.x) != 0;
}
// 函数运算
friend constexpr FloatPointNumber sqrtl(FloatPointNumber a) {
if (a.val() <= 0) {
return 0;
}
return FloatPointNumber(sqrtl(a.x));
}
friend constexpr FloatPointNumber sinl(FloatPointNumber a) {
return FloatPointNumber(sinl(a.x));
}
friend constexpr FloatPointNumber cosl(FloatPointNumber a) {
return FloatPointNumber(cosl(a.x));
}
friend constexpr FloatPointNumber abs(FloatPointNumber a) {
return FloatPointNumber(std::fabs(a.x));
}
// 输入输出
friend constexpr std::istream &operator>>(std::istream &is, FloatPointNumber &a) {
is >> inputStr;
if constexpr (std::is_same<T, long double>::value) {
a = FloatPointNumber(std::stold(inputStr));
} else {
a = FloatPointNumber(std::stod(inputStr));
}
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, FloatPointNumber a) {
return os << std::fixed << std::setprecision(precision) << a.val();
}
// 常数
static constexpr FloatPointNumber PI = FloatPointNumber(acosl(-1));
};
template <class T>
std::string FloatPointNumber<T>::inputStr;
template <class T>
int FloatPointNumber<T>::precision = 12;
using Float = FloatPointNumber<double>;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
assert(1 <= n and n <= 200'000);
assert(k <= n);
std::vector<int> a(n + 1);
for (int i = 0; i < n; i++) {
std::cin >> a[i + 1];
assert(1 <= a[i + 1] and a[i + 1] <= 1000);
}
auto check = [&](Float V) {
std::vector<Float> f{0};
Float s = 0;
int p = 0;
for (int i = 1; i <= n; i++) {
s += a[i] - V;
if (s < 0) {
continue;
}
p = std::lower_bound(begin(f), end(f), s) - begin(f);
if (p == f.size()) {
f.push_back(s);
} else {
f[p] = s;
}
}
return p >= k;
};
Float l = 0, r = 1001;
for (int i = 0; i < 60; i++) {
Float mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
std::cout << std::fixed << std::setprecision(12) << r << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
input:
7 3 1 3 1 2 2 2 1
output:
1.666666666666
result:
ok found '1.66667', expected '1.66667', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1 1 1
output:
0.999999999999
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 4020kb
input:
2 1 2 1
output:
1.999999999999
result:
wrong answer 1st numbers differ - expected: '1.50000', found: '2.00000', error = '0.50000'