QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#749586#9540. Double 11hos_lyricWA 0ms3984kbC++143.3kb2024-11-15 05:24:512024-11-15 05:24:52

Judging History

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

  • [2024-11-15 05:24:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3984kb
  • [2024-11-15 05:24:51]
  • 提交

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'