Hamako Online Judge

TLE
8sec

MLE
512MB

得点
100

問題

ミズゴロウのゴロウくんは, 花を育てている. 毎日水やりをすることで, 日々花は美しくなっていく. 最近, ゴロウくんは花の水やりのスケジュールを立てるのに悩んでいる. ゴロウくんのために, 時刻 0 から時刻 T までの花の水やりのスケジュールを立てるのを手伝ってあげよう.

ゴロウくんは N 本の花を育てていて, N 本は一直線上に咲いている. それぞれの花にはみずみずしさがあり, 時刻 0 の時点で左から i 番目の花のみずみずしさは A_i という正の整数で表される. それぞれの花のみずみずしさは, 時刻が 1 増えると, その瞬間に B_i だけ減少する. ここで, 花のみずみずしさが 0 以下になるとその花は枯れてしまう. そこで, 時刻 i と時刻 i + 1 (0 ≤ i ≤ T - 1) の間に, 次の水やりという操作を行うことが出来る.

水やり : 左から i 番目の花を花 i とする. 1 つ花を選ぶ(ここでは花 x を選んだとする). このとき, 花 x - K から花 x + K までのそれぞれの花のみずみずしさを C だけ増やす. (みずみずしさが時刻 0 での初期値 A_i を超える可能性があることに注意せよ.) ここで x - K が 0 以下になる場合は 1 番目の花まで, x + K が N を超える場合は N 番目の花までみずみずしさが増えるとする.

ゴロウくんは水やりに慣れているため, 時刻 i と時刻 i + 1 (0 ≤ i ≤ T - 1) の間に何度でも水やりを行うことが出来る. まったく水やりを行わない時刻があっても構わない. また, 同じ花に対して何回も水やりを行っても良い. しかし, ゴロウくんはできるだけ水やりを行う回数を減らしたいと考えている. ゴロウくんのために, 時刻 T までに花を枯らさないよう水やりを行うとき, その回数の最小値を求めるプログラムを作成せよ.

入力

1 行目に, 4 つの整数 N, K, C, T (1 ≤ N ≤ 5 × 10⁶, 0 ≤ K ≤ [N / 2], 1 ≤ C ≤ 10⁷, 1 ≤ T ≤ 1000) が空白区切りで入力される. ここで, [N / 2] は N / 2 の整数部分を表す.

2 行目に, 4 つの整数 Sa, Xa, Ya, Za (0 ≤ Sa, Xa, Ya ≤ 10⁷ - 1, 1 ≤ Za ≤ 10⁷) が空白区切りで入力される. Sa, Xa, Ya < Za が保証されている.

3 行目に, 4 つの整数 Sb, Xb, Yb, Zb (0 ≤ Sb, Xb, Yb ≤ 10⁷ - 1, 1 ≤ Zb ≤ 10⁷) が空白区切りで入力される. Sb, Xb, Yb < Zb が保証されている.

2, 3 行目の整数を用いて, 問題文中で与えられている A_i と B_i は以下の C++ 言語のコードで生成される. Xa と Sa の積 (Xb と Sb の積) が 32 ビット符号付き整数に収まらない可能性があることに注意せよ.

void generate(int A[], int B[])
{
    for (int i = 1; i <= N; i++){
        A[i] = Sa + 1;
        B[i] = Sb + 1;
        Sa = (Xa * Sa + Ya) % Za;
        Sb = (Xb * Sb + Yb) % Zb;
    }
}

出力

1 行に, 時刻 T までに水やりを行う回数の最小値を出力せよ.

入出力例

入力例 1

3 0 1 5
1 1 5 11
0 0 0 1

出力例 1

入力例 1 について, それぞれの花の時刻 0 でのみずみずしさ Ai と, 花のみずみずしさの減少量 Bi は次のようになっている :
A₁ = 2, A₂ = 7, A₃ = 1,
B₁ = 1, B₂ = 1, B₃ = 1.
次の水やりの仕方は, 最小の水やりの回数である 9 回を達成できる例である.

時刻 0 と時刻 1 の間 : この時点での花のみずみずしさは, 花 1 から順番に 2, 7, 1 である. 水やりを行わないと, 時刻 1 での花 3 のみずみずしさが 0 になってしまう. よって, 時刻 0 と時刻 1 の間に 1 回水やりを行い, 花のみずみずしさをそれぞれ 2, 7, 2 としておく.
時刻 1 と時刻 2 の間 : この時点での花のみずみずしさは, 花 1 から順番に 1, 6, 1 である. 水やりを行わないと, 時刻 2 での花のみずみずしさがそれぞれ 0, 5, 0 になってしまう. よって, 時刻 1 と時刻 2 の間に 2 回水やりを行い, 花のみずみずしさをそれぞれ 2, 6, 2 としておく.
時刻 2 と時刻 3 の間 : この時点での花のみずみずしさは, 花 1 から順番に 1, 5, 1 である. 水やりを行わないと, 時刻 3 での花のみずみずしさがそれぞれ 0, 4, 0 になってしまう. よって, 時刻 2 と時刻 3 の間に 2 回水やりを行い, 花のみずみずしさをそれぞれ 2, 5, 2 としておく.
時刻 3 と時刻 4 の間 : この時点での花のみずみずしさは, 花 1 から順番に 1, 4, 1 である. 水やりを行わないと, 時刻 4 での花のみずみずしさがそれぞれ 0, 3, 0 になってしまう. よって, 時刻 3 と時刻 4 の間に 2 回水やりを行い, 花のみずみずしさをそれぞれ 2, 4, 2 としておく.
時刻 4 と時刻 5 の間 : この時点での花のみずみずしさは, 花 1 から順番に 1, 3, 1 である. 水やりを行わないと, 時刻 5 での花のみずみずしさがそれぞれ 0, 2, 0 になってしまう. よって, 時刻 4 と時刻 5 の間に 2 回水やりを行い, 花のみずみずしさをそれぞれ 2, 3, 2 としておく.

入力例 2

16 3 8 5
9 9 8 47
0 2 9 37

出力例 2

入力例 2 の最初の 5 本の花のみずみずしさ Ai と, 花のみずみずしさの減少量 Bi は次のようになっている :
A₁ = 10, A₂ = 43, A₃ = 11, A₄ = 5, A₅ = 45,
B₁ = 1, B₂ = 10, B₃ = 28, B₄ = 27, B₅ = 25.

入力例 3

1234567 89 1 987
7777779 6543210 6172819 10000000
584 5849 58499 5849999

出力例 3

37025278961263

入力例 3 の答えが 32 ビット符号付き整数の範囲を超えていることに注意せよ.

005 - 楽しい楽しい花の水やり (Watering Flower is So Fun)

問題

入力