民间数据TLE两个点,求优化思路
查看原帖
民间数据TLE两个点,求优化思路
736062
bengshakala1楼主2022/12/7 09:48
#include <iostream>
using namespace std;

#define MD 998244353
#define MAXN 1005

struct PI{
	int d;
	int r;
};

int mp[MAXN][MAXN];
PI ln[MAXN][MAXN];

void init_m(/*int mp[][MAXN],PI ln[][MAXN],*/long n,long m)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			char tmp;
			cin>>tmp;
			mp[i][j]=tmp-'0';
			ln[i][j].d=ln[i][j].r=0;
		}
	for(int i=n-1;i>=0;i--)
	{
		ln[i][m].r=-1;
		for(int j=m-1;j>=0;j--)
		{
			if(mp[i][j]==1)
				ln[i][j].r=-1;
			else
				ln[i][j].r=ln[i][j+1].r+1;
		}
	}
	for(int i=m-1;i>=0;i--)
    {
        ln[n][i].d=-1;
        for(int j=n-1;j>=0;j--)
        {
            if(mp[j][i]==1)
                ln[j][i].d=-1;
            else
                ln[j][i].d=ln[j+1][i].d+1;
        }
    }
}


void solve(long n,long m,long &rc,long &rf)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			if(mp[i][j] || mp[i+1][j] || mp[i+2][j])
				continue;
			int top=ln[i][j].r;
			int len_d=ln[i][j].d;
			for(int a=i+2;a<=i+len_d;a++)
			{
				rc+=((top*ln[a][j].r)%MD);
				rf+=((top*ln[a][j].r*ln[a][j].d)%MD);
				rc%=MD;rf%=MD;
			}
		}
	return;
}	

int main()
{
	int T,id;
	cin>>T>>id;
	for(int TT=0;TT<T;TT++)
	{
		long n,m,c,f,rc=0,rf=0;
		cin>>n>>m>>c>>f;
		init_m(n,m);
		solve(n,m,rc,rf);
		c=(rc*c)%MD;f=(rf*f)%MD;
		cout<<c<<' '<<f<<endl;
	}
	return 0;
}
2022/12/7 09:48
加载中...