盖亚!!!!!!!(洛谷过了,其他冥间数据超时,求助)
查看原帖
盖亚!!!!!!!(洛谷过了,其他冥间数据超时,求助)
230825
许多楼主2021/11/7 09:45
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
inline long long read(){
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	return x*f;
}
long long n,m1,m2;
struct qwe{
	long long a,b;
}a1a[100100],a2a[100100];
bool Cmp(qwe a,qwe b){
	return a.a<b.a;
}
long long ans=-1,a1[100100],a2[100100];
int main(){
	n=read();m1=read();m2=read();
	for(int i=1;i<=m1;i++)a1a[i].a=read(),a1a[i].b=read();
	for(int i=1;i<=m2;i++)a2a[i].a=read(),a2a[i].b=read();
	
	sort(a1a+1,a1a+1+m1,Cmp);
	sort(a2a+1,a2a+1+m2,Cmp);
	if(m1+m2<=n){
		printf("%lld",m1+m2);
		return 0;
	}
	
	int qwe1[100100];memset(qwe1,0,sizeof(qwe1));
	for(int i=1;i<=m1;i++) for(int j=1;j<=100000;j++)if(qwe1[j]<a1a[i].a){qwe1[j]=a1a[i].b,a1[j]++;break;}
	
	int qwe2[100100];memset(qwe2,0,sizeof(qwe2));
	for(int i=1;i<=m2;i++) for(int j=1;j<=100000;j++)if(qwe2[j]<a2a[i].a){qwe2[j]=a2a[i].b,a2[j]++;break;}
	
	for(int i=2;i<=100000;i++)a1[i]+=a1[i-1],a2[i]+=a2[i-1];
	
	long long k=min(n,m1);
	for(int i=n-m2>=0? n-m2:0;i<=k;i++){
		int j=n-i;ans=max(a1[i]+a2[j],ans);
	}
	
	printf("%lld",ans);
	return 0;
}
2021/11/7 09:45
加载中...