求助,样例能过,但是大数据炸了?
查看原帖
求助,样例能过,但是大数据炸了?
1215295
discretely楼主2024/2/28 22:05
// Problem: 
//     P1868 饥饿的奶牛
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1868
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<algorithm>
using namespace std;

const int N=3e6+10;
#define int long long
struct node{
	int x,y;
}a[150005];
int f[N];
bool cmp(node a,node b){
	return a.y<b.y;
}

signed main(){
	int n;cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].x>>a[i].y;
	} 
	sort(a+1,a+1+n,cmp);
	//前几个都是0   for(int i=1;i<a[1].y) f[i]=0;
	int now=0;
	for(int i=1;i<=n;++i){
		int k=a[i].y-a[i].x+1;
		if(a[i].x<=now) f[a[i].y]=max(f[now],f[a[i].x-1]+k);
		else f[a[i].y]=f[now]+k;
		now=a[i].y;
	}
	cout<<f[a[n].y]<<endl;
	
	
	
	
	return 0;
}
2024/2/28 22:05
加载中...