求助CF1082C为什么TLE
  • 板块学术版
  • 楼主lgmulti
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/1/17 13:10
  • 上次更新2023/11/5 04:44:34
查看原帖
求助CF1082C为什么TLE
54769
lgmulti楼主2021/1/17 13:10
#include<iostream>
#include<queue>
using namespace std;

int n,m,u,v;
priority_queue<int> sub[100005];
int fssub[100005]={0};
int nextt[100005]={0},prevv[100005]={0};
int ans=0;

int fread(){
	int i,j;
	int delta=1;
	int ans=0;
	char ch;
	do{
		ch=getchar();
	}while((ch<'0' || ch>'9') && ch!='-');
	if(ch=='-')
		delta=-1;
	do{
		if(ch>='0' && ch<='9')
			ans=ans*10+(ch-'0');
		ch=getchar();
	}while(ch>='0' && ch<='9');
	return ans*delta;
}

int main(){
	int i,j;
	n=fread(); m=fread();
	for(i=0;i<=m;i++){
		nextt[i]=i+1;
		prevv[i]=i-1;
	}
	for(i=0;i<n;i++){
		u=fread(); v=fread();
		sub[u].push(v);
	}

	for(i=0;i<n;i++){
		bool flag=0;
		for(j=nextt[0];j<=m;j=nextt[j]){
			if(!sub[j].empty()){
				fssub[j]+=sub[j].top();
				sub[j].pop();
				flag=1;
			}	
			else
				nextt[prevv[j]]=nextt[j];
		}
		if(!flag)
			break;

		int tmp=0;
		for(j=nextt[0];j<=m;j=nextt[j]){
			if(fssub[j]>0 && nextt[prevv[j]]==j)
				tmp+=fssub[j];
		}
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}
2021/1/17 13:10
加载中...