QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397379 | #7567. Joining Cats | ucup-team1338# | WA | 1ms | 7912kb | C++23 | 949b | 2024-04-24 00:07:08 | 2024-04-24 00:07:08 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5005;
int dp[maxn][maxn];
int p[maxn][maxn],p2[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&&t<=k) 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++)
{
for(int j=1;j<=k;j++)
{
p2[p[i][j]][j]=i;
}
}
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][j],p[dp[i-1][j]][i]);
dp[p2[j][i]][j]=max(dp[p2[j][i]][j],dp[i-1][j]);
}
}
printf(dp[k][1]==n+1?"Yes\n":"No\n");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7816kb
input:
5 2 1 1 1 1 1 2 2
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 7912kb
input:
6 7 3 2 1 1 2 3 2 2 2 2 2 2 2
output:
No
result:
ok answer is NO
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 7756kb
input:
7 4 1 2 3 4 3 2 1 3 3 3 3
output:
No
result:
wrong answer expected YES, found NO