记录编号	41634	评测结果	AAAAAAAAAA
题目名称	环保绿化	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.077 s
提交时间	2012-08-06 17:01:20	内存使用	0.46 MiB

#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=30100;
class Tree
{
public:
    int s,e,t;
}T[5100];
int N,H,ans=0;
int hash[MAXN];
 
bool cmp(const Tree&a,const Tree&b)
{
    if(a.e!=b.e) return a.e<b.e;
    return a.s>b.s;
}
 
inline void init()
{
    scanf("%d\n%d\n",&N,&H);
    for(int i=1;i<=H;i++)
        scanf("%d%d%d",&T[i].s,&T[i].e,&T[i].t);
    sort(T+1,T+1+H,cmp);
}
 
inline void greedy()
{
    int have,next;  
    for(int i=2;i<=H;i++)
    {
        have=0;
        for(int j=T[i].s;j<=T[i].e;j++)
            if(hash[j]) have++;
        if(have>=T[i].t) continue;
        next=T[i].t-have;
        for(int j=T[i].e;j>=T[i].s;j--)
        {
            if(hash[j]) continue;
            hash[j]=1; ans++;
            next--; if(!next) break;
        }
    }
}
 
int main()
{
    freopen("trees.in","r",stdin);
    freopen("trees.out","w",stdout);
    init();
    for(int i=T[1].e;i>=T[1].s;i--)
    {
        ans++; hash[i]=1;
        if(ans==T[1].t) break;
    }
    greedy();
    printf("%d\n",ans);
    return 0;
}