数据过水
查看原帖
数据过水
926840
封禁用户楼主2023/10/5 22:24

想法:b=x⋅t+y⋅t′b = x \cdot t + y \cdot t'。

枚举,O(qn3)O(qn^3),加了俩优化就过了并且 76 ms。

#include<bits/stdc++.h>
using namespace std;
int b[2005],c[2005],t[2005],n;
int pd(int x,int y){
	for(int i=1;i<=n;i++){
		if(x*b[i]+y*c[i]>t[i]) return -1;
		if(x*b[i]+y*c[i]<t[i]) return 0;
	}
	return 1;
}
int read(){
	int x=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-') f=-1;c=getchar();}
	while(c>47&&c<58) x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x*f;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		memset(c,0,sizeof(c));
		n=read();
		int mx=0;
		for(int i=1;i<=n;i++)
			b[i]=read(),c[i]+=b[i],c[n-i+1]+=b[i];
		for(int i=1;i<=n;i++)
			t[i]=read(),mx=max(mx,t[i]);
		bool flag=0;
		for(int i=0;i<=mx;i++){
			for(int j=0;j<=mx;j++){
				int kkk=pd(i,j);
				if(kkk==-1) break;
				if(kkk){
					flag=1;
					break;
				}
			} 
			if(flag) break;
		}
		if(flag==1) cout<<"yes\n";
		else cout<<"no\n";
	}
	return 0;
}
2023/10/5 22:24
加载中...