QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216587#7567. Joining CatsEastKingWA 8ms101484kbC++172.1kb2023-10-15 20:13:472023-10-15 20:13:47

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 20:13:47]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:101484kb
  • [2023-10-15 20:13:47]
  • 提交

answer

	#include<bits/stdc++.h>
	using namespace std;
	const int M=5005;
	int n,K;
	int w[M],s[M],ms[M];
	long long sum[M];
	int dis[M][M];
	int nxt[M][13];
	int calcl(int l,int r,int lim){
		int ans=r+1;
		while(l<=r){
			int mid=l+r>>1;
			if(sum[r]-sum[mid-1]<=lim){
				ans=mid;
				r=mid-1;
			}else {
				l=mid+1;
			}
		}
		return ans;
	}
	int calcr(int l,int r,int lim){
		int ans=l-1;
		while(l<=r){
			int mid=l+r>>1;
			if(sum[mid]-sum[l-1]<=lim){
				ans=mid;
				l=mid+1;
			}else {
				r=mid-1;
			}
		}
		return ans;
	}
	struct node{
		int d,l,r;
		bool operator <(const node &tmp)const{
			return d>tmp.d;
		}
	};
	int get_K(int p,int lim){
		if(s[p]>=lim)return p;
		for(int i=12;i>=0;i--){
			if(s[nxt[p][i]]>=lim)continue;
			p=nxt[p][i]; 
		}
		return nxt[p][0];
	}
	void bfs(){
		memset(dis,63,sizeof(dis));
		priority_queue<node>Q; 
		for(int i=1;i<=n;i++){
			dis[i][i]=0;
			Q.push({0,i,i});
		}
		while(!Q.empty()){
			node now=Q.top();
			Q.pop();
			int l=now.l,r=now.r;
			if(now.d>dis[l][r])continue;
			//printf("dis[%d][%d]=%d\n",l,r,dis[l][r]);
			int k=dis[l][r]+1;
			if(k>K)continue;
			if(l>1){
				int p=get_K(k,w[l-1]);
				//printf("pl=%d\n",p);
				if(p<=K){
					int ql=calcl(1,l-1,s[p]);
					if(ql==1&&r==n)return ;
					if(dis[ql][r]>p){
						dis[ql][r]=p;
						Q.push({p,ql,r});
					}
				}
			}
			if(r<n){
				int p=get_K(k,w[r+1]);
				//printf("pr=%d\n",p);
				if(p<=K){
					int qr=calcr(r+1,n,s[p]);
					if(l==1&&qr==n)return ;
					if(dis[l][qr]>p){
						dis[l][qr]=p;
						Q.push({p,l,qr});
					} 
				}
			}
		}
	}
	int main(){
		scanf("%d %d",&n,&K);
		for(int i=1;i<=n;i++){
			scanf("%d",&w[i]);
			sum[i]=sum[i-1]+w[i];
		}
		for(int i=1;i<=K;i++){
			scanf("%d",&s[i]);
		}
		for(int i=K;i>=0;i--){
			int x=i+1;
			while(x<K+1){
				if(s[i]>=s[x])x=nxt[x][0];
				else break;
			}
			nxt[i][0]=x;
		}
		for(int j=1;j<13;j++){
			for(int i=0;i<=n;i++){
				nxt[i][j]=nxt[nxt[i][j-1]][j-1];
			}
		}
		bfs();
		if(dis[1][n]<=K)printf("Yes\n");
		else printf("No\n");
		return 0; 
	}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 101484kb

input:

5 2
1 1 1 1 1
2 2

output:

No

result:

wrong answer expected YES, found NO