TLE*2 求助后缀和如何优化

#include<iostream>
#include<cstdio>
using namespace std;
int a[1010][1010];
int st[1010][1010],ph[1010][1010];
int t,id,n,m,c,f;
char cc;
int main(){
	
	scanf("%d%d",&t,&id);
	
	for(int kkksc03=1;kkksc03<=t;kkksc03++){
		scanf("%d%d%d%d",&n,&m,&c,&f);
		if(c==0&&f==0){
		    cout<<0<<' '<<0<<endl;
		    continue;
	    }
	    
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>cc;
				a[i][j]=cc-48;
				st[i][j]=0;
				ph[i][j]=0;
			}  
		}
		
	    long long sumc=0,sumf=0;
	    for(int i=1;i<=n;i++){
	    	st[i][m]=!a[i][m];
	    	for(int j=m-1;j>=1;j--){
	    		st[i][j]=st[i][j+1]+1;
	    		if(a[i][j]==1)st[i][j]=0;
			}
		} 
		for(int j=1;j<=m;j++){
	    	ph[n][j]=!a[n][j];
	    	for(int i=n-1;i>=1;i--){
	    	    ph[i][j]=ph[i+1][j]+1;
	    		if(a[i][j]==1)ph[i][j]=0;
		    }
		}//后缀和 
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				st[i][j]=max(st[i][j]-1,0);
				ph[i][j]=max(ph[i][j]-1,0);
			}
		}
		
	    for(int i=1;i<=n-2;i++){
	    	for(int j=1;j<=m-1;j++){
	    		if(ph[i][j]&&st[i][j]){
	    			for(int k=i+2;k<=i+ph[i][j];k++){
	    				sumc+=st[i][j]*st[k][j];
	    				sumf+=st[i][j]*st[k][j]*ph[k][j];
					}
				}
			}
		}
		long long s1=sumc*c%998244353,s2=sumf*f%998244353;
		printf("%lld %lld\n",s1,s2);
	}
	return 0;
}