记录编号	605646	评测结果	AAAAA
题目名称	284.[NOI 1999]内存分配	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.123 s
提交时间	2025-09-05 20:29:54	内存使用	3.74 MiB

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3fffffff
using namespace std;
const int N=10010;
int n,w=INF,cnt=0;
struct work
{
    int t,m,p,s;
    bool operator <(const work& x)const{
        return s<x.s;
    }
}x;
vector<work> data;
queue<work> wait;
bool wk_in(int t)
{
    if(data.empty()||data[0].s>=x.m){
        x.s=0;
        x.t=t;
        data.push_back(x);
        sort(data.begin(),data.end());
        return true;
    }
    for(int i=1;i<data.size();i++){
        if(data[i].s-(data[i-1].s+data[i-1].m)>=x.m){
            x.s=data[i-1].s+data[i-1].m;
            x.t=t;
            data.push_back(x);
            sort(data.begin(),data.end());
            return true;
        }
    }
    int sz=data.size();
    if(n-(data[sz-1].s+data[sz-1].m)>=x.m){
        x.s=data[sz-1].s+data[sz-1].m;
        x.t=t;
        data.push_back(x);
        sort(data.begin(),data.end());
        return true;
    }
    return false;
}
void wk_out()
{
    int nw=INF;
    for(int i=0;i<data.size();i++)
        if(data[i].t+data[i].p==w) data.erase(data.begin()+i--);
        else nw=min(nw,data[i].t+data[i].p);
    while(wait.size()){
        x=wait.front();
        if(wk_in(w)){
            nw=min(nw,wait.front().t+wait.front().p);
            wait.pop();
            cnt++;
        }else break;
    }
    w=nw;
    return;
}
void wk(int t,int m,int p)
{
    while(t>=w) wk_out();
    x.t=t;
    x.m=m;
    x.p=p;
    if(wk_in(t)) w=min(w,t+p);
    else wait.push(x);
    return;
}
int main()
{
    freopen("memory.in","r",stdin);
    freopen("memory.out","w",stdout);
    
    cin>>n;
    int t1,m1,p1;
    cin>>t1>>m1>>p1;
    while(t1!=0||m1!=0||p1!=0){
        wk(t1,m1,p1);
        cin>>t1>>m1>>p1;
    }
    while(wait.size()) wk_out();
    int ans=w;
    for(int i=0;i<data.size();i++) ans=max(ans,data[i].t+data[i].p);
    cout<<ans<<endl;
    cout<<cnt<<endl;
    return 0;
}