求助 WA#3 看了一下大数据似乎过不去?
查看原帖
求助 WA#3 看了一下大数据似乎过不去?
1215295
discretely楼主2024/2/29 01:28
#include<iostream>
#include<algorithm>
using namespace std;
const int N=4e6;
struct node{
	int x,y,s;
}a[N];
int f[N];
bool cmp(node a,node b){
	return a.x==b.x ? a.y < b.y : a.x < b.x;
}


int main(){
    int n;cin>>n;
    int r=0;
    for(int i=1;i<=n;++i){
    	cin>>a[i].x>>a[i].y;
    	a[i].s=a[i].y-a[i].x+1;
    	r=max(r,a[i].y);
    }
    sort(a+1,a+1+n,cmp);
    int j=1;
    for(int i=1;i<=r;++i){
    	f[i]=max(f[i],f[i-1]);
    	while(a[j].x==i&&j<=n){
    		f[a[j].y]=max(f[a[j].y],f[a[j].x-1]+a[j].s);
    		++j;
    	}
    }
    cout<<f[r]<<endl;
	
	
	return 0;
}
2024/2/29 01:28
加载中...