QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216587 | #7567. Joining Cats | EastKing | WA | 8ms | 101484kb | C++17 | 2.1kb | 2023-10-15 20:13:47 | 2023-10-15 20:13:47 |
Judging History
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