比赛 |
2024暑期C班集训2 |
评测结果 |
AATTTTTWTT |
题目名称 |
雨滴之歌 |
最终得分 |
20 |
用户昵称 |
123 |
运行时间 |
7.588 s |
代码语言 |
C++ |
内存使用 |
267.87 MiB |
提交时间 |
2024-07-02 11:28:47 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=5050;
long long g[N][N];
int a[N],b[N],n,m,vis[N][N],ret=0;
int dx[]={0,1};
int dy[]={1,0};
void bfs(int x)
{
memset(vis,0,sizeof(vis));
queue<pair<int,int>> q;
q.push(make_pair(x,1));
vis[x][1]=1;
while (!q.empty())
{
pair<int,int> t;
t=q.front();q.pop();
for (int i=0;i<2;i++)
{
int nowx=t.first+dx[i],nowy=t.second+dy[i];
if (nowx<=n && nowy<=m && !vis[nowx][nowy] && g[nowx][nowy]>=0)
{
q.push(make_pair(nowx,nowy));
vis[nowx][nowy]=1;
if (nowy==m)
{
ret++;
}
}
}
}
}
int main() {
freopen("expansion.in","r",stdin);
freopen("expansion.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for (int i=1;i<=m;i++)
{
scanf("%d",&b[i]);
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
g[i][j]=a[i]+b[j];
}
}
for (int i=1;i<=n;i++)
{
if (g[i][1]>=0)
{
bfs(i);
}
}
printf("%d",ret);
}