結果
問題 | No.463 魔法使いのすごろく🎲 |
ユーザー |
|
提出日時 | 2016-12-14 00:53:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,310 bytes |
コンパイル時間 | 1,646 ms |
コンパイル使用メモリ | 173,156 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-11-30 02:02:27 |
合計ジャッジ時間 | 83,042 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 1 TLE * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<class T>class RangeMinimumQuery {private:int numLeaves;vector<T> nodes;public:RangeMinimumQuery(int n) {numLeaves = 1 << (int)log2(n * 2 - 1);nodes.resize(numLeaves * 2, numeric_limits<T>::max());}RangeMinimumQuery(const vector<T> &a) {numLeaves = 1 << (int)log2(a.size() * 2 - 1);nodes.resize(numLeaves * 2, numeric_limits<T>::max());for (int i = 0; i < a.size(); i++) {nodes[i + numLeaves] = a[i];}for (int i = numLeaves - 1; i >= 1; i--) {nodes[i] = min(nodes[i * 2], nodes[i * 2 + 1]);}}// 0-indexedvoid setValue(int index, T value) {nodes[index + numLeaves] = value;for (int i = index + numLeaves; i > 1; i >>= 1) {nodes[i >> 1] = min(nodes[i], nodes[i ^ 1]);}}// 0-indexed [l,r)T minimum(int l, int r) {T result = numeric_limits<T>::max();l += numLeaves;r += numLeaves;for (; l < r; l >>= 1, r >>= 1) {if (l & 1) {result = min(result, nodes[l++]);}if (r & 1) {result = min(result, nodes[--r]);}}return result;}};template<class T>class FenwickTree {private:vector<T> nodes;public:FenwickTree(int n) : nodes(n + 1) {}// 0-indexedvoid add(int index, T value) {for (int i = index + 1; i < nodes.size(); i += i & -i) {nodes[i] += value;}}// 0-indexed [0, index)T sum(int index) {T result = 0;for (int i = index; i > 0; i &= i - 1) {result += nodes[i];}return result;}// 0-indexed [l, r)T sum(int l, int r) {return sum(r) - sum(l);}};int main() {int n, m;cin >> n >> m;const int M = n * 2 - 2;vector<double> c(M * 2);for (int i = 1; i < n - 1; i++) {cin >> c[i];}for (int i = 0; i < n - 2; i++) {c[n + i] = c[n - 2 - i];}for (int i = 0; i < M; i++) {c[i + M] = c[i];}const int T = 30000000 / M;vector<double> E(M * 2), EE(M * 2);for (int ii = 0; ii < T; ii++) {RangeMinimumQuery<double> rmq(M * 2);FenwickTree<double> ftE(M * 2);FenwickTree<double> ftEE(M * 2);for (int i = 0; i < M; i++) {E[i + M] = E[i];EE[i + M] = EE[i];E[i] = 0;EE[i] = 0;rmq.setValue(i + M, EE[i + M] + c[i + M]);ftE.add(i + M, E[i + M] + c[i + M]);ftEE.add(i + M, EE[i + M] + c[i + M]);}for (int i = M - 1; i >= 0; i--) {if (i == n - 1) {E[i] = 0;EE[i] = 0;} else {double mini = rmq.minimum(i + 1, i + m + 1);E[i] += ftE.sum(i + 1, i + m + 1) / m;EE[i] += ftEE.sum(i + 1, i + m + 1) / m;E[i] = min(E[i], mini);}rmq.setValue(i, EE[i] + c[i]);ftE.add(i, E[i] + c[i]);ftEE.add(i, EE[i] + c[i]);}}printf("%.20f\n", (double)min(E[0], EE[0]));}