合計は $(A+B+C)～(A+B+C+3)$ の間の任意の値を取れる。この中に $S$ が入っていればよい。
a = int(input())
b = int(input())
c = int(input())
s = int(input())
print('Yes' if a + b + c <= s <= a + b + c + 3 else 'No')
未確定の房は $B$ であった方が明らかに合計が大きくなるので、最大値を求める上では $B$ と考えてよい。
制約が小さいので、シミュレーションする。
$N$ 要素の配列を用意して、$B$ で初期化する。
それぞれの情報で $l_i～r_i$ のみかんを $A$ にする。
n, m, a, b = map(int, input().split())
mikan = [b] * n
for _ in range(m):
l, r = map(int, input().split())
for m in range(l - 1, r):
mikan[m] = a
print(sum(mikan))
これらを踏まえ、以下のように問題は言い換えられる。
実際にやってみると、以下のことが分かる。
解法としてDPと当たりを付け、$dp_{i,k}$ を「$1～i$ 番目までの石山だけに注目して、$k$ 回操作した後の状態数」としたとする。
だがこのままでは、なかなか遷移が難しい。実際に簡単な例で試してみる。
石山の初期状態 : {1, 2, 3}
i=1
iまでの石山の初期状態: {1}
0回操作で {1} の1通り
1回(以上)操作で {0} の1通り
i=2
iまでの石山の初期状態: {1, 2}
0回操作で {1, 2} の1通り
1回操作で {0, 2}, {1, 1} の2通り
2回操作で {0, 2}, {0, 1}, {1, 0} の3通り
3回操作で {0, 2}, {0, 1}, {1, 0}, {0, 0} の4通り
4回以上の操作ではずっと4通り
i=3
iまでの石山の初期状態: {1, 2, 3}
操作回数 0 1 2 3 4 5 6以上
パターン数 1 3 6 10 14 17 18
どういう計算で遷移させればよいか？ 法則性が見えづらい。
ややこしくしている原因は0個の石山の扱いにあって、
もう一つDPに区別を設け、$dp_{i,k,j}$ とし、$j$ を0か1の値を取る「0個の石山が含まれるかフラグ」とすれば遷移はやりやすそう。
また区別することで「各操作で、0個の石山は選ばない（常にどこかから石を取る）」とルールを設けてもよくなり、これにより空間の問題も解消する。
どういうことかというと、$k$ 回の操作後に0個の石山が含まれている場合は、$k+1,k+2,...$ 回の操作後の全ての場合においてその状態が実現可能。なので $K=k+1$ の時の答えを求めたければ、$K=1～k$ の、0個の石山を含む状態数から取ってこれるので、dp(k+1)自身が持つ必要が無い。
これにより考慮すべき $k$ の上限が $cnt_i$ の総和までとなり、各 $cnt_i$ は $log_2{10^{18}}=60$ 程度までなので、$N=50$ でも3000程度となり、十分小さくなる。
石山の初期状態 : {1, 2, 3}
便宜上、dp(i,k,j) の j=0をdp0, j=1をdp1と表現する
i=1
k __0__1___
dp0 : 1 0 # 0個の石山を含まない場合
dp1 : 0 1 # 0個の石山を含む場合
0回の操作後は {1} の、0個の石山を含まない場合が1通り
1回の操作後は {0} の、0個の石山を含む場合が1通り
2回以上は操作を行えない
i=2
k __0__1__2__3__
dp0 : 1 1
dp1 : 1 2 1
1回の操作後は {0, 2}, {1, 1} それぞれ0個の石山を含む場合と含まない場合が1通りずつ
2回の操作後は {0, 1}, {1, 0} 0個の石山を含む場合が2通り
※{0, 2} も元のルールでは2回の操作後に実現可能だが、
0個の石山に対して操作しないとならず、
1回の操作後で既にカウントされているのでここでは考慮しない
3回の操作後は {0, 0} 0個の石山を含む場合が1通り
i=3
k __0__1__2__3__4__5__6__
dp0 : 1 2 2 1
dp1 : 1 3 5 5 3 1
各操作後の状態は省略
K=3の時の状態数を求める時は、
dp0からはそのまま取ってきて1通り。
dp1からは、3以下の状態数を合計して 1+3+5=9通り。
計10通り
いずれの遷移も、$dp_i$ の状態のみから $dp_{i+1}$ を決定できる。
$dp0_{i,k}$ からは、$dp0_{i+1}$ と $dp1_{i+1}$ の両方に遷移する。
まず、$dp0_{i+1,k+q}$（ただし $q=0,1,...,cnt_{i+1}-1$）に状態数は引き継がれる。
これは、$i+1$ 個目の石山を、0個減らした場合、1個減らした場合、……、$cnt_{i+1}-1$ 個減らした場合を意味している。石山は0にしてはいけないのでその直前まで。
また、$dp1_{i+1,k+cnt_{i+1}}$ に引き継がれる。
これは、$i+1$ 個目の石山に $cnt_{i+1}$ 回操作を加えて0にした場合を意味している。
$dp1_{i,k}$ からは、$dp1_{i+1}$ に遷移する。
$dp1_{i+1,k+q}$（ただし $q=0,1,...,cnt_{i+1}$）に引き継がれる。
これは、$i+1$ 個目の石山を、0個減らした場合、1個減らした場合、……を意味している。こちらは0まで減らしてもよい。
$K$ が $cnt_i$ の総和（$cnt_1+cnt_2+...+cnt_N$）以上の場合、つまり、全ての石山を0にするのに十分な場合、簡単に計算できる。$cnt_i$ の総和以上の $K$ では、既に取り得る全ての状態を数え上げているので、それ以上 $K$ が増えても答えが増えることはない。
$i$ 個目の石山のみに着目すると、$0,1,2,...,cnt_i$ の $cnt_i+1$ 通りの状態を取れる。
全ての状態数(仮)は、$(cnt_1+1)\times(cnt_2+1)\times ... \times(cnt_N+1)$ となる。
ただしこの中には、$K$ 回の操作では不可能なものもある。それは全ての石山が0でない状態。$K$ 回操作すると、少なくとも1つの石山は必ず0にせざるを得ない。逆に少なくとも1つの石山が0であれば、$K$ 回の操作後でも可能となる。
よって、状態数(仮)から全ての石山が0でない $cnt_1 \times cnt_2 \times ... \times cnt_N$ 通りを除けば、答えが求まる。
この枝刈りをしておけば、保持すべき $K$ の上限は $cnt_i$ の総和までとなり、空間の問題については解決する。（まぁ結局遷移が難しいんですけど）
def dividable(a):
if a == 0:
return 0
return len(bin(a)) - 2
def solve(n, k, aaa):
ddd = list(map(dividable, aaa))
s = sum(ddd)
if k >= s:
ans = 1
exc = 1
for d in ddd:
ans *= (d + 1)
ans %= MOD
exc *= d
exc %= MOD
return (ans - exc) % MOD
dp0 = [1]
dp1 = [0]
for d in ddd:
ndp0 = [0] * (len(dp0) + d)
ndp1 = [0] * (len(dp0) + d)
for i, (p0, p1) in enumerate(zip(dp0, dp1)):
for q in range(d):
ndp0[i + q] += p0
ndp1[i + q] += p1
ndp1[i + d] += p0 + p1
dp0 = ndp0
dp1 = ndp1
print(dp0)
print(dp1)
return (dp0[k] + sum(dp1[:k + 1])) % MOD
MOD = 1000000007
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, k, aaa))
$i$ 番目のガソリンスタンドを $GS_i$ と表す。
$GS_i$ で補充後、次に補充できる可能性のあるGSは、座標 $x_i+(F-T) \lt x_k \le x_i+F$ にある $GS_k$ となる。
FULL NEXT NEXT NEXT ↓ x1 --- x2 x3 x4 ------ x5 -- x6 -- x7 ----- x8 <--- F-T ---> <----------------- F ----------------->
DPを考える。$dp_{i}=$「$GS_i$ で補充することになるような、$GS_1,GS_2,...,GS_{i-1}$ の取り壊され方のパターン数」とする。
上の例で、$GS_1$ で補充し、次に補充するGSを考える。
これを先頭からDPで配っていけばよい。座標0の出発地点を $GS_0$ と見なし、$dp_0=1$ としてそこから始める。
答えの数え上げは、最後に給油することになりえる（つまり、$x_i+F \ge D$）各 $GS_i$ につき、残ってても通過するGSの数 $t$ を求め、$dp_i \times 2^t$ を加算する。
最後に給油
↓
xi --- x x x -------- x x x ----- D
<----- F-T ----->
<-------------------- F -----------...->
`---------------'|`--------------'
残ってても通過する|xiを最後の給油地点にするためには
GSは3個 |必ず取り壊されてないといけない
ANS += dp[i] * 2^3
実装は、区間への足し込みを行うため、BITなどを使って累積和で管理する。が、もっと速い提出があるのでよりよい方法はありそう（たぶんbisectで探してる部分は尺取り法でいける）。BITではMODを取ることに注意。
import bisect
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s % MOD
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
self.tree[i] %= MOD
i += i & -i
MOD = 1000000007
d, f, t, n = map(int, input().split())
xxx = [0] + list(map(int, input().split()))
r = f - t
dp = Bit(n + 2)
dp.add(1, 1)
dp.add(2, -1)
reachable = d - f
ans = 0
for i, x in enumerate(xxx):
i += 1
s = dp.sum(i)
if s == 0:
continue
ti = bisect.bisect(xxx, x + r, lo=i)
fi = bisect.bisect(xxx, x + f, lo=ti)
inc = s * pow(2, ti - i, MOD) % MOD
if ti < fi:
dp.add(ti + 1, inc)
dp.add(fi + 1, -inc)
if x >= reachable:
ans += inc
ans %= MOD
print(ans)