记录编号	605614	评测结果	AAAAA
题目名称	284.[NOI 1999]内存分配	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.261 s
提交时间	2025-09-05 18:51:32	内存使用	3.75 MiB

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

ll n,m,w,ans;
struct node{
	ll t,m,p,id;
}a;
vector<node> p;
queue<node> q;

bool cmp(node a,node b){
	return a.id<b.id;
}

bool workin(ll t){
	if(p.empty()||p[0].id>=a.m){
		a.id=0;
		a.t=t;
		p.push_back(a);
		sort(p.begin(),p.end(),cmp);
		return 1;
	}
	ll k=p.size();
	for(int i=1;i<k;i++){
		if(p[i].id-(p[i-1].id+p[i-1].m)>=a.m){
			a.id=p[i-1].id+p[i-1].m;
			a.t=t;
			p.push_back(a);
			sort(p.begin(),p.end(),cmp);
			return 1;
		}
	}
	ll zn=k-1;
	if(n-(p[zn].id+p[zn].m)>=a.m){
			a.id=p[zn].id+p[zn].m;
			a.t=t;
			p.push_back(a);
			sort(p.begin(),p.end(),cmp);
			return 1;
	}
	return 0;
}
void workout(){
	ll nw=1e9;
	for(int i=0;i<p.size();i++){
		if(p[i].t+p[i].p==w){
			p.erase(p.begin()+i);i--;
		}else{
			nw=min(nw,p[i].t+p[i].p);
		}
	}
	while(q.size()){
		a=q.front();
		if(workin(w)){
			nw=min(nw,a.t+a.p);
			q.pop();
			ans++;
		}
		else break;
	}
	w=nw;
}
void work(ll t,ll m,ll p){
	while(t>=w)workout();
	a.t=t;
	a.m=m;
	a.p=p;
	if(workin(t))w=min(w,t+p);
	else q.push(a);
}
int main(){
	freopen("memory.in","r",stdin);
	freopen("memory.out","w",stdout);
	cin>>n;
	for(int gg=1;gg;gg++){
		ll x,y,z;
		cin>>x>>y>>z;
		if(x==0&&y==0&&z==0){
			m=gg-1;
			break;
		}
		work(x,y,z);
	}
	while(q.size()){
		workout();
	}
	ll anss=0;
	for(int i=0;i<p.size();i++){
		anss=max(anss,p[i].t+p[i].p);	
	}
	cout<<anss<<"\n"<<ans;
	return 0;
}