AOJ 2250: Operator

たまに見る二分探索トラップ。
嘘解法ごめんなさい……。

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[1100];
int d[1100];
int e[1100];
int fin[1100];
int next[1100];
int a,b;
int can(int M){
	for(int i=0;i<M;i++)fin[i]=0;
	for(int i=0;i<a;i++)next[i]=0;
	int last=0;
	int rem=a;
	for(int i=0;i<b;i++){
		for(int j=0;j<M;j++){
			if(fin[j]<=i){
				for(int k=0;k<a;k++){
					if(~next[k]&&next[k]<=i){
						next[k]=-1;
						fin[j]=i+c[k];
						last=max(last,fin[j]);
						rem--;
						break;
					}
				}
			}
		}
		for(int j=0;j<a;j++){
			if(~next[j]&&i==next[j]+d[j]){
				next[j]=next[j]+d[j]+e[j];
			}
		}
		if(!rem)break;
	}
	for(int i=0;i<a;i++)if(~next[i])last=9999999;
	if(last<=b)return 1;
	return 0;
}
int main(){
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)scanf("%d%d%d",c+i,d+i,e+i);
		int left=0;
		int right=1001;
		while(left+1<right){
			int M=(left+right)/2;
			if(can(M)){
				right=M;
			}else left=M;
		}
		int tr=right;
		for(int i=1;i<=10&&tr-i>0;i++){
			if(can(tr-i))right=tr-i;
		}
		printf("%d\n",right);
	}
}