Language: C++

[AtCoder Beginner Contest 154 D - Dice in Line](https://atcoder.jp/contests/abc154/tasks/abc154_d)

## 問題文
N個のサイコロが左から右に一列に並べてあります。左からi番目のサイコロは1からp<sub>i</sub>までのp<sub>i</sub>種類の目がそれぞれ等確率で出ます。  
隣接するK個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

### 制約
* 1≤K≤N≤200000
* 1≤p<sub>i</sub>≤1000
* 入力で与えられる値は全て整数

### 入力
入力は以下の形式で標準入力から与えられる。
```
N K
p1 ... pN
```

### 出力
隣接するK個のサイコロを選んで振ったときに出る目の合計の期待値の最大値を出力せよ。  
なお、想定解答との絶対誤差または相対誤差が10<sup>−6</sup>以下であれば正解として扱われる。

## 考察
* 最初のK個の和を取り、K+1個目を足し、1個目を引くといった感じで計算すれば、Kが大きくても計算量は大きくならないと考えた。
* 相対誤差について書いてあったが、今回は期待値=(1+p<sub>i</sub>)/2は0.5単位にしかならないので、考慮する必要はなさそう。

## ソースコード
```
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int ll

#define FOR(i,m,n) for(int i=(m); i<(n); ++i)
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
typedef vector<P> vp;
typedef queue<P> Q;
inline int in() { int x; cin >> x; return x; }

void solve() {
  int n = in(), d2 = in()*2, a = in();
  vp p(n); for(auto &a : p) a = {in(),in()}; sort(all(p));
  int ans = 0, damage = 0;
  Q q;
  FOR(i,0,n) {
    int x, h; tie(x,h) = p[i];
    while (!q.empty() && q.front().first < x) {
      damage -= q.front().second; q.pop();
    }
    h -= damage;
    if (h>0) {
      int t = (h+a-1)/a;
      int at = a*t;
      ans += t;
      damage += at;
      q.push({x+d2, at});
    }
  }
  cout << fixed << setprecision(7) << ans << endl;
}

#undef int
int main() {
  solve();
  return 0;
}
```

Compiler output:
a.cc:3:1: error: stray '##' in program
    3 | ## 問題文
      | ^~
a.cc:4:1: error: extended character 。 is not valid in an identifier
    4 | N個のサイコロが左から右に一列に並べてあります。左からi番目のサイコロは1からp<sub>i</sub>までのp<sub>i</sub>種類の目がそれぞれ等確率で出ます。
      | ^
a.cc:4:108: error: extended character 。 is not valid in an identifier
    4 | N個のサイコロが左から右に一列に並べてあります。左からi番目のサイコロは1からp<sub>i</sub>までのp<sub>i</sub>種類の目がそれぞれ等確率で出ます。
      |                                                                                                            ^
a.cc:5:1: error: extended character 、 is not valid in an identifier
    5 | 隣接するK個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。
      | ^
a.cc:5:1: error: extended character 。 is not valid in an identifier
a.cc:7:1: error: stray '##' in program
    7 | ### 制約
      | ^~
a.cc:7:3: error: stray '#' in program
    7 | ### 制約
      |   ^
a.cc:8:3: error: extended character ≤ is not valid in an identifier
    8 | * 1≤K≤N≤200000
      |   ^
a.cc:8:3: error: extended character ≤ is not valid in an identifier
a.cc:8:3: error: extended character ≤ is not valid in an identifier
a.cc:9:3: error: extended character ≤ is not valid in an identifier
    9 | * 1≤p<sub>i</sub>≤1000
      |   ^
a.cc:9:18: error: extended character ≤ is not valid in an identifier
    9 | * 1≤p<sub>i</sub>≤1000
      |                  ^
a.cc:12:1: error: stray '##' in program
   12 | ### 入力
      | ^~
a.cc:12:3: error: stray '#' in program
   12 | ### 入力
      |   ^
a.cc:13:1: error: extended character 。 is not valid in an identifier
   13 | 入力は以下の形式で標準入力から与えられる。
      | ^
a.cc:14:1: error: stray '`' in program
   14 | ```
      | ^
a.cc:14:2: error: stray '`' in program
   14 | ```
      |  ^
a.cc:14:3: error: stray '`' in program
   14 | ```
      |   ^
a.cc:17:1: error: stray '`' in program
   17 | ```
      | ^
a.cc:17:2: error: stray '`' in program
   17 | ```
      |  ^
a.cc:17:3: error: stray '`' in program
   17 | ```
      |   ^
a.cc:19:1: error: stray '##' in program
   19 | ### 出力
      | ^~
a.cc:19:3: error: stray '#' in program
   19 | ### 出力
      |   ^
a.cc:20:1: error: extended character 。 is not valid in an identifier
   20 | 隣接するK個のサイコロを選んで振ったときに出る目の合計の期待値の最大値を出力せよ。
      | ^
a.cc:21:1: error: extended character 、 is not valid in an identifier
   21 | なお、想定解答との絶対誤差または相対誤差が10<sup>−6</sup>以下であれば正解として扱われる。
      | ^
a.cc:21:50: error: extended character − is not valid in an identifier
   21 | なお、想定解答との絶対誤差または相対誤差が10<sup>−6</sup>以下であれば正解として扱われる。
      |                                                  ^
a.cc:21:58: error: extended character 。 is not valid in an identifier
   21 | なお、想定解答との絶対誤差または相対誤差が10<sup>−6</sup>以下であれば正解として扱われる。
      |                                                          ^
a.cc:23:1: error: stray '##' in program
   23 | ## 考察
      | ^~
a.cc:24:3: error: extended character 、 is not valid in an identifier
   24 | * 最初のK個の和を取り、K+1個目を足し、1個目を引くといった感じで計算すれば、Kが大きくても計算量は大きくならないと考えた。
      |   ^
a.cc:24:26: error: extended character 、 is not valid in an identifier
   24 | * 最初のK個の和を取り、K+1個目を足し、1個目を引くといった感じで計算すれば、Kが大きくても計算量は大きくならないと考えた。
      |                          ^
a.cc:24:26: error: extended character 、 is not valid in an identifier
a.cc:24:26: error: extended character 。 is not valid in an identifier
a.cc:25:3: error: extended character 、 is not valid in an identifier
   25 | * 相対誤差について書いてあったが、今回は期待値=(1+p<sub>i</sub>)/2は0.5単位にしかならないので、考慮する必要はなさそう。
      |   ^
a.cc:25:66: error: extended character 、 is not valid in an identifier
   25 | * 相対誤差について書いてあったが、今回は期待値=(1+p<sub>i</sub>)/2は0.5単位にしかならないので、考慮する必要はなさそう。
      |                                                                  ^
a.cc:25:66: error: extended character 。 is not valid in an identifier
a.cc:27:1: error: stray '##' in program
   27 | ## ソースコード
      | ^~
a.cc:28:1: error: stray '`' in program
   28 | ```
      | ^
a.cc:28:2: error: stray '`' in program
   28 | ```
      |  ^
a.cc:28:3: error: stray '`' in program
   28 | ```
      |   ^
a.cc:68:1: error: stray '`' in program
   68 | ```
      | ^
a.cc:68:2: error: stray '`' in program
   68 | ```
      |  ^
a.cc:68:3: error: stray '`' in program
   68 | ```
      |   ^
a.cc:1:1: error: expected unqualified-id before '[' token
    1 | [AtCoder Beginner Contest 154 D - Dice in Line](https://atcoder.jp/contests/abc154/tasks/abc154_d)
      | ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:29:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~