QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#600478 | #7567. Joining Cats | ucup-team073# | RE | 0ms | 0kb | C++14 | 1.3kb | 2024-09-29 16:50:37 | 2024-09-29 16:50:38 |
answer
#include <bits/stdc++.h>
// #define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())f^=ch=='-';
for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
return f?x:-x;
}
inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}
const int N=5005;
int n,k,f[N][N],a[N],s[N],t[N][N];
int main(){
freopen("test.out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;++i){
a[i]=read();
f[0][i]=i;
}
for(int i=1;i<=k;++i){
s[i]=read();
int sum=0;
for(int l=1,r=1;l<=n;++l){
while(r<=n&&sum+a[r]<=s[i])sum+=a[r++];
t[i][l]=r-1;
sum-=a[l];
}
}
// for(int i=1;i<=k;++i,puts("")){
// for(int j=1;j<=n;++j){
// printf("t[%d][%d]=%d ",i,j,t[i][j]);
// }
// }
for(int x=1;x<=k;++x){
for(int i=1;i<=n;++i){
chmax(f[x][i],t[x][f[x-1][i]+1]);
chmax(f[x][i],f[x-1][t[x][i]+1]);
}
for(int i=1;i<=n;++i){
chmax(f[x][i],f[x-1][i]);
if(i-1)chmax(f[x][i],f[x-1][i-1]);
}
}
if(f[k][1]>=n)puts("Yes");
else puts("No");
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
5 2 1 1 1 1 1 2 2