比赛 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);
}