求助
查看原帖
求助
782898
Time_Limit_Exceed楼主2022/10/24 12:56
using namespace std;
#define int long long
const int N=5e5+10;
int x[N],y[N],v[N];
int a[N],p[N];
bool vis[N];
struct Node{
	int num,x;
}b[N];
bool cmp(Node x1,Node x2){
	if(x1.x==x2.x) return x1.num<x2.num;
	return x1.x>x2.x;
}
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=(s*10)+(ch-'0');
		ch=getchar();
	}
	return s*f;
}
signed main(){
	int n=read(),m=read();
	for(int i=1;i<=n;i++){
		x[i]=read(),y[i]=read(),v[i]=read();
	}
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(y[i]!=y[j]) continue;
			if(v[i]==v[j]){
				if(x[i]==x[j]) ++p[i],++p[j];
				continue;
			}
			if(x[i]==x[j]) continue;
			if(x[i]>x[j]){
				if(v[i]>v[j]) continue;
			}
			else if(v[i]<v[j]) continue;
			double ans=2.0*(v[i]-v[j])*min(y[i],y[j]);
			ans=ans/1.0/(x[j]-x[i]);
			if(ans>=9.8) ++p[i],++p[j];
		}
	}
	for(int i=1;i<=n;i++){
	    b[i].num=i;
		b[i].x=min(a[i],p[i]);
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=m;i++){
		vis[b[i].num]=1;
	}
	int s=0;
	for(int i=1;i<=n;i++){
		if(vis[i]){
			if(p[i]>a[i]) s+=p[i]-a[i];
		}
		else s+=p[i];
	}
	printf("%lld\n",s);
	return 0;
}


纯暴力,可只有5pts,或许是我题意没有读懂?
2022/10/24 12:56
加载中...