QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609285#8524. Weather ForecastCappsWA 0ms4020kbC++205.1kb2024-10-04 11:46:542024-10-04 11:46:56

Judging History

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

  • [2024-10-04 11:46:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4020kb
  • [2024-10-04 11:46:54]
  • 提交

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'