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

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
 
ll n;
struct node{
    int t,m,p,h;
    friend bool operator<(node x,node y){
        return x.h < y.h;
    }
};
 
node a;
int k = inf;
int sum = 0;

queue<node> q;
vector<node> v;


bool qin(int t){
    if(v.empty() || v[0].h >= a.m){
        a.h = 0;
        a.t = t;
        v.push_back(a);
        sort(v.begin(), v.end());
        return true;
    }
    for(int i = 1; i < v.size(); i++){
        if(v[i].h - (v[i-1].h + v[i-1].m) >= a.m){
            a.h = v[i-1].h + v[i-1].m;
            a.t = t;
            v.push_back(a);
            sort(v.begin(), v.end());
            return true;
        }
    }
    int sz = v.size();
    if (n - (v[sz-1].h + v[sz-1].m) >= a.m) {
        a.h = v[sz-1].h + v[sz-1].m;
        a.t = t;
        v.push_back(a);
        sort(v.begin(), v.end());
        return true;
    }
    return false;
}

void qpop(){
    int fk = inf;
    for(int i = 0; i < v.size(); i++){
        if(v[i].t + v[i].p == k){
            v.erase(v.begin() + i);
            i--;
        }
        else{
            fk = min(fk, v[i].t + v[i].p);
        }
    }
    while(!q.empty()){
        a = q.front();
        if(qin(k)){
            fk = min(fk, a.t + a.p);
            q.pop();
            sum++;
        }
        else{
            break;
        }
    }
    k = fk;
}


void solv(int t, int m, int p){
    while(t >= k){
        qpop();
    }
    a.t = t;
    a.m = m;
    a.p = p;
    if(qin(t)){
        k = min(k, t + p);
    }
    else{
        q.push(a);
    }
}
 
 
int main(){
	
	freopen("memory.in", "r", stdin);
    freopen("memory.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    
    int t, m, p;
    while(cin >> t >> m >> p){
        if(t == 0 && m == 0 && p == 0){
            break;
        }
        solv(t, m, p);
    }
    
    while(!q.empty()){
        qpop();
    }
    
    int ans = 0;
    for(int i = 0; i < v.size(); i++){
        int u = v[i].t + v[i].p;
        ans = max(ans, u);
    }
    ans = max(ans, k);
    
    cout << ans << "\n" << sum << endl;
    
    return 0;
}