C++14(g++5.4) 解法, 执行用时: 38ms, 内存消耗: 3432K, 提交时间: 2020-03-24 16:00:22

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

const int N = 5e4+5;
vector<pair<int,int> > G[N];
int d[N];
bool v[N];
int n;


int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a++, b++;
        G[a-1].emplace_back(b,c);
    }
    for(int i=1;i<N;i++) G[i].emplace_back(i-1,-1), G[i-1].emplace_back(i,0); 
    fill(d,d+N,-100000000);
    d[0] = 0;
    v[0] = 1;
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        v[x] = 0;
        for(auto p:G[x]) {
            int y = p.first, z = p.second;
            if(d[y]<d[x] + z) {
                d[y] = d[x] + z;
                if(!v[y]) q.push(y), v[y] = 1;
            }
        }
    }
    cout<<d[N-1]<<endl;
    return 0;
}

C++(clang++11) 解法, 执行用时: 9ms, 内存消耗: 512K, 提交时间: 2020-10-26 11:40:26

#include <bits/stdc++.h>
using namespace std;
const int maxn=50000;
struct abc
{
	int l,r,c;
};
bool cmp(abc f1,abc f2)
{
	if(f1.l==f2.l)
	{
		if(f1.r==f2.r)
		{
			return f1.c>f2.c;
		}
		return f1.r>f2.r;
	}
	return f1.l>f2.l;
}
int main()
{
	int n;
	cin>>n;
	abc a[n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].l>>a[i].r>>a[i].c;
	}
	sort(a+1,a+1+n,cmp);
	int v[maxn];
	memset(v,0,sizeof(v));
	int p=0;
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=a[i].l;j<=a[i].r;j++)
		{
			if(v[j]==1)	ans++;
		}
		ans=a[i].c-ans;
		if(ans<=0)	continue;
		for(int j=a[i].l;j<=a[i].r;j++)
		{
			if(v[j]==0)
			{
				p++;
				v[j]=1;
				ans--;
				if(ans==0)	break;
			}
		}
	}
	cout<<p<<endl;
    return 0;
}