レストランに存在する卵の「仕入れた日」を、キューで管理することを考えます。
このとき、空のキューから始めて、\(i\) 日目の朝・昼・夜の行動に対応する操作はそれぞれ次のようになります。

• キューの末尾に \(i\) を \(A_i\) 個追加する。
• キューの先頭から \(B_i\) 個の要素を削除する。
• キューの先頭の要素が \((i-D)\) である限り、キューの先頭の要素を削除する。

ここで、夜の行動について、キューの要素はつねに先頭から末尾に向けて昇順となっており、\((i-D-1)\) 日目以前に仕入れられた卵は前日までに削除されているため、キューの要素に \((i-D)\) が含まれるかを確認するには、キューの先頭の要素が \((i-D)\) であるかを確認すれば十分であることに注意してください。

求めるべき答えは、これを \(i=1,2,\ldots,N\) の順で行った後のキューの要素数になります。

それぞれの操作を行う回数について、各テストケースにおいてキューに追加される要素の数は \((A_1+A_2+\cdots+A_N)\) 個であり、よって削除される要素の個数も高々その個数です。 よって、キューに対する追加・削除操作が \(O(1)\) で行えることから、時間計算量は \(O(N\max(A_i))\) です。
問題の制約より、各入力における \(N\) の総和は高々 \(2\times 10^5\) であり、\(\max(A_i)\leq 10\) とあわせて十分高速です。
よって、この問題を解くことができました。

他にも、\(i\) 日目に仕入れた卵がいくつ残っているかを配列の \(i\) 番目の要素に格納・更新して管理する方法などもあります。その場合は、毎回 \(D\) 日分の在庫を確認すると \(\Theta(ND)\) の時間計算量がかかって実行時間制限に引っかかるため、現在所持している卵の中で最も古いものが何日目に仕入れたものであるかの情報もあわせて更新していく必要があることに注意してください。

C++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int t;
	cin>>t;
	
	for(int itest=0;itest<t;itest++){
		int n,d;
		cin>>n>>d;

		vector<int>a(n),b(n);
		for(int i=0;i<n;i++)cin>>a[i];
		for(int i=0;i<n;i++)cin>>b[i];

		int x;
		queue<int>q;
		for(int i=0;i<n;i++){
			for(int j=0;j<a[i];j++)q.push(i);
			for(int j=0;j<b[i];j++)q.pop();
			while((!q.empty())&&(q.front()==i-d))q.pop();
		}
		cout<<((int)(q.size()))<<endl;
	}
	return 0;
}