记录编号	605654	评测结果	AAAAA
题目名称	284.[NOI 1999]内存分配	最终得分	100
用户昵称	xxz	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2025-09-05 21:39:52	内存使用	3.85 MiB

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
int n, w = INF, cnt, ans, t0, m0, p0, nw;
struct mem
{
	int t, m, p, s;
	bool operator<(const mem &x) const
	{
		return s < x.s;
	}
};
vector<mem> p;
queue<mem> q;
mem x;
bool enter(int t)
{
	if (p.empty() || p[0].s >= x.m)
	{
		x.s = 0;
		x.t = t;
		p.push_back(x);
		sort(p.begin(), p.end());
		return 1;
	}
	for (int i = 1; i < p.size(); i++)
	{
		if (p[i].s - (p[i - 1].s + p[i - 1].m) >= x.m)
		{
			x.s = p[i - 1].s + p[i - 1].m;
			x.t = t;
			p.push_back(x);
			sort(p.begin(), p.end());
			return 1;
		}
	}
	if (n - (p[p.size() - 1].s + p[p.size() - 1].m) >= x.m)
	{
		x.s = p[p.size() - 1].s + p[p.size() - 1].m;
		x.t = t;
		p.push_back(x);
		sort(p.begin(), p.end());
		return 1;
	}
	return 0;
}
void release()
{
	nw = INF;
	for (int i = 0; i < p.size(); i++)
		if (p[i].t + p[i].p == w)
			p.erase(p.begin() + i--);
		else
			nw = min(nw, p[i].t + p[i].p);
	while (q.size())
	{
		x = q.front();
		if (enter(w))
		{
			nw = min(nw, q.front().t + q.front().p);
			q.pop();
			cnt++;
		}
		else
			break;
	}
	w = nw;
	return;
}
void work(int t, int m, int p)
{
	while (t >= w)
		release();
	x.t = t;
	x.m = m;
	x.p = p;
	if (enter(t))
		w = min(w, t + p);
	else
		q.push(x);
	return;
}
signed main()
{
	freopen("memory.in", "r", stdin);
	freopen("memory.out", "w", stdout);
	cin >> n;
	while (1)
	{
		scanf("%lld%lld%lld", &t0, &m0, &p0);
		if (!t0 && !m0 && !p0)
			break;
		work(t0, m0, p0);
	}
	while (!q.empty())
		release();
	ans = w;
	for (int i = 0; i < p.size(); i++)
		ans = max(ans, p[i].t + p[i].p);
	cout << ans << endl
		 << cnt;
	return 0;
}