Official

F - 安全装置 / Safety System Editorial by QCFium


この問題は問題文の記述をうまくプログラムに落とし込めれば正解することができます。

以下のものを持ちながらタスクの処理をシミュレートします。

  • 今何番目のタスクの最初か
  • 今の瞬間の負荷 \(L\) 以上のタスクの連続処理時間

そのタスクが負荷 \(L\) 以上か、\(L\) 以上ならば今のタスクの途中で安全装置が作動するか、またはタスクの終了と同時に作動するかなどの場合分けを使うことでシミュレートすることができます。
forever の判定も同時にすることができますし、forever となる条件は「負荷 \(L\) 以上、かつ処理時間が \(T\) を超えるタスクが存在する」なのでこれを最初に判定してもよいです。

解答例 (C++)

#include <stdio.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int l = ri();
	int t = ri();
	int x = ri();
	
	int a[n], b[n];
	for (int i = 0; i < n; i++) a[i] = ri(), b[i] = ri();
	for (int i = 0; i < n; i++) if (b[i] >= l && a[i] > t) {
		puts("forever");
		return 0;
	}
	
	int res = 0;
	int heavy_consec = 0;
	for (int i = 0; i < n; ) {
		if (b[i] >= l && heavy_consec + a[i] >= t) {
			res += t - heavy_consec + x;
			if (heavy_consec + a[i] == t) i++;
			heavy_consec = 0;
		} else {
			res += a[i];
			if (b[i] >= l) heavy_consec += a[i];
			else heavy_consec = 0;
			i++;
		}
	}
	printf("%d\n", res);
	
	return 0;
}

posted:
last update: