RT

int calc1(int i, int k) {
	return f[i - w - 1][k] + k * ap[i];
}

int calc2(int i, int k) {
	return f[i - w - 1][k] + k * bp[i];
}

for (int i = 1; i <= t; i ++) {
		for (int k = 0; k <= as[i]; k ++)
			f[i][k] = -k * ap[i];
		q1[l1 = r1 = 1] = 0, q2[l2 = r2 = 1] = 0;
		if (i - w - 1 >= 1)
			for (int k = 1; k <= bs[i]; k ++) {// 初始化卖股票窗口
				while (l2 <= r2 && calc2(i, q2[r2]) <= calc2(i, k)) r2 --;
				q2[++ r2] = k;
			}
		for (int j = 0; j <= m; j ++) {
			f[i][j] = max(f[i - 1][j], f[i][j]);
			if (i - w - 1 >= 1) {
				if (j - 1 >= 0) {
					while (l1 <= r1 && calc1(i, q1[r1]) <= calc1(i, j - 1)) r1 --;
					q1[++ r1] = j - 1;
				}
				while (l1 <= r1 && q1[l1] < j - as[i]) l1 ++;
				if (l1 <= r1) f[i][j] = max(calc1(i, q1[l1]) - j * ap[i], f[i][j]);
				
				if (j + bs[i] <= m) {
					while (l2 <= r2 && calc2(i, q2[r2]) <= calc2(i, j + bs[i])) r2 --;
					q2[++ r2] = j + bs[i];
				}
				while (l2 <= r2 && q2[l2] < j + 1) l2 ++;
				if (l2 <= r2) f[i][j] = max(calc2(i, q2[l2]) - j * bp[i], f[i][j]);
			}
		}
	}