QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397359 | #7567. Joining Cats | ucup-team1338# | RE | 0ms | 0kb | C++23 | 820b | 2024-04-23 23:38:28 | 2024-04-23 23:38:29 |
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5005;
int dp[maxn][maxn];
int p[maxn][maxn];
int w[maxn],s[maxn];
struct V{
int id,val;
bool operator <(const V& b){return val<b.val;}
}v[maxn];
int main()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=k;i++) cin>>s[i],v[i].id=i,v[i].val=s[i];
sort(v+1,v+1+k);
for(int i=1;i<=n;i++)
{
long long sum=0;int t=1;
for(int j=i;j<=n;j++)
{
sum+=w[j];
while(sum>v[t].val) p[i][v[t].id]=j,t++;
}
while(t<=k) p[i][v[t].id]=n+1,t++;
}
for(int i=1;i<=n;i++) dp[0][i]=i+1;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=max(dp[i-1][p[j][i]],p[dp[i-1][j]][i]);
}
}
//printf("%d ",dp[k][1]);
printf(dp[k][1]==n+1?"Yes\n":"no");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 2 1 1 1 1 1 2 2