#23

/*
Though leaves are many, the root is one;
Through all the lying days of my youth
I swayed my leaves and flowers in the sun,
Now may I wither into the truth.
 
- William Butler Yeats
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
#include <bitset>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;
 
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
#define dbg if(false)
/**==Info==
*Program:1
*Problem:Rhombus
*Date:2019-12-30
*Algorithm:My rubbish prefix sum and violence
*Status:Unknown*/
 
bool debug=false;
 
ll n,m,k;
ll a[1005][1005];
ll tri[4][1005][1005];
 
ll colsum[1005][1005],rowsum[1005][1005];
 
int dsuid[1005][1005],dsuind[1005][1005];
ll dsusum[2005][2005];
int dsdid[1005][1005],dsdind[1005][1005];
ll dsdsum[2005][2005];
ll f[1005][1005];
 
int dsuic,dsdic;
 
const int L=0,R=1;
 
void runDsu(int x,int y){
	int cnt=0;
	
	while(true){
		dsuid[x][y]=dsuic;
		dsuind[x][y]=cnt;
		dsusum[dsuic][cnt]=(cnt==0?0:dsusum[dsuic][cnt-1])+a[x][y];
		cnt++;
		x--;y++;
		if(x<0 || y>=m){
			break;
		}
	}
	dsuic++;
}
 
void runDsd(int x,int y){
	int cnt=0;
	
	while(true){
		dsdid[x][y]=dsdic;
		dsdind[x][y]=cnt;
		dsdsum[dsdic][cnt]=(cnt==0?0:dsdsum[dsdic][cnt-1])+a[x][y];
		cnt++;
		x++;y++;
		if(x>=n || y>=m){
			break;
		}
	}
	dsdic++;
}
 
inline ll getCS(int col,int st,int ed){
	if(st>ed){
		swap(st,ed);
	}
	
	return colsum[col][ed]-(st==0?0:colsum[col][st-1]);
}
 
//inline int getDSUId(int x,int y){
//	return dsuid[x][y];
//}
//
//inline int getDSUInd(int x,int y){
//	return dsuind[x][y];
//}
//
//inline int getDSDId(int x,int y){
//	return dsdid[x][y];
//}
//
//inline int getDSDInd(int x,int y){
//	return dsdind[x][y];
//}
 
inline ll getDSU(int id,int st,int ed){
	if(st>ed){
		swap(st,ed);
	}
	
	return dsusum[id][ed]-(st==0?0:dsusum[id][st-1]);
}
 
inline ll getDSD(int id,int st,int ed){
	if(st>ed){
		swap(st,ed);
	}
	
	return dsdsum[id][ed]-(st==0?0:dsdsum[id][st-1]);
}
 
inline ll getDSU(int x1,int y1,int x2,int y2){
	dbg cout<<"DSU="<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dsuid[x1][y1]<<" "<<dsuid[x2][y2]<<endl;
	
	assert(dsuid[x1][y1]==dsuid[x2][y2]);
	return getDSU(dsuid[x1][y1],dsuind[x1][y1],dsuind[x2][y2]);
}
inline ll getDSD(int x1,int y1,int x2,int y2){
	dbg cout<<"DSD="<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dsdid[x1][y1]<<" "<<dsdid[x2][y2]<<endl;
	assert(dsdid[x1][y1]==dsdid[x2][y2]);
	return getDSD(dsdid[x1][y1],dsdind[x1][y1],dsdind[x2][y2]);
}
 
inline ll getRS(int rownum,int l,int r){
	if(l>r){
		swap(l,r);
	}
	
	return rowsum[rownum][r]-(l==0?0:rowsum[rownum][l-1]);
}
 
void proceedL(){
	
	for(int i=k-1;i<=n-k;i++){
		int up=k-1;
		for(int j=0;j<k;j++){
			tri[L][i][k-1]+=getCS(k-1-j,i-up,i+up);
			up--;
		}
	}
	
	
	for(int i=k-1;i<=n-k;i++){
		dbg cout<<"Doing line "<<i<<endl;
		for(int j=k;j<=m-k;j++){
			dbg cout<<"Solving for column "<<j<<endl;
			
			ll p1=tri[L][i][j-1];
			ll p2=getCS(j,i-k+1,i+k-1);
			ll p3=getDSU(i,j-k,i-k+1,j-1);
			ll p4=getDSD(i,j-k,i+k-1,j-1);
			ll p5=a[i][j-k];
			
			dbg cout<<i<<" "<<j<<" p="<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<endl;
			tri[L][i][j]=p1+p2-p3-p4+p5;
		}
		
	}
	
//	dbg{
		ll mx=0; 
		for(int i=k-1;i<=n-k;i++){
			for(int j=k-1;j<=m-k;j++){
				mx=max(mx,tri[L][i][j]);
			}
		}
		cout<<mx<<endl;
		exit(0);
//	}
}
 
void proceedR(){
	
	for(int i=k-1;i<=n-k;i++){
		int up=k-1;
		for(int j=0;j<k;j++){
			tri[R][i][k-1]+=getCS(k-1+j,i-up,i+up);
			up--;
		}
	}
	
	
	for(int i=k-1;i<=n-k;i++){
		dbg cout<<"Doing line "<<i<<endl;
		for(int j=k;j<=m-k;j++){
			dbg cout<<"Solving for column "<<j<<endl;
			
			ll p1=tri[R][i][j-1];
			ll p2=getCS(j-1,i-k+1,i+k-1);
			ll p3=getDSD(i,j+k-1,i-k+1,j);
			ll p4=getDSU(i,j+k-1,i+k-1,j);
			ll p5=a[i][j+k-1];
			
			dbg cout<<i<<" "<<j<<" p="<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<endl;
			tri[R][i][j]=p1-p2+p3+p4-p5;
		}
		
	}
	
	dbg{
		for(int i=k-1;i<=n-k;i++){
			for(int j=k-1;j<=m-k;j++){
				cout<<tri[R][i][j]<<" ";
			}
			cout<<endl;
		}
	}
}
 
int main(int argc,char* argv[]){
	qi;
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	
	//calc for the col sum
	for(int i=0;i<m;i++){
		colsum[i][0]=a[0][i];
		for(int j=1;j<n;j++){
			colsum[i][j]=colsum[i][j-1]+a[j][i];
		}
	}
	
	for(int i=0;i<n;i++){
		rowsum[i][0]=a[i][0];
		for(int j=1;j<m;j++){
			rowsum[i][j]=rowsum[i][j-1]+a[i][j];
		}
	}
	
	//calc for the dsu
	for(int i=0;i<n;i++){
		runDsu(i,0);
	}
	for(int i=1;i<m;i++){
		runDsu(n-1,i);
	}
	
	dbg{
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				printf("(%d,%d) in dsu %d ind= %d sum_until=%d\t",i,j,dsuid[i][j],dsuind[i][j],dsusum[dsuid[i][j]][dsuind[i][j]]);
			}
			printf("\n");
		}
	}
	
	//calc for dsd
	for(int i=n-1;i>=0;i--){
		runDsd(i,0);
	}
	for(int i=1;i<m;i++){
		runDsd(0,i);
	}
	
	dbg{
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				printf("(%d,%d) in dsd %d ind= %d sum_until=%d\t",i,j,dsdid[i][j],dsdind[i][j],dsdsum[dsdid[i][j]][dsdind[i][j]]);
			}
			printf("\n");
		}
	}
	
	proceedL();
	proceedR();
	
	//calc left up corner answer
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
//			cout<<i<<' '<<j<<" "<<a[i][j]<<" "<<max(0,k-abs(i-(k-1))-abs(j-(k-1)))<<endl;
			f[k-1][k-1]+=a[i][j]*max(0ll,k-abs(i-(k-1))-abs(j-(k-1)));
		}
	}
	
	dbg cout<<"ini="<<f[k-1][k-1]<<endl;
	
	//move to the right
	for(int i=k-1;i<=n-k;i++){
		for(int j=k;j<=m-k;j++){
			//move
			ll p1=f[i][j-1];
			ll p2=tri[R][i][j];
			ll p3=tri[L][i][j-1];
			
			dbg cout<<"F "<<i<<" "<<j<<"="<<p1<<"+"<<p2<<"-"<<p3<<endl;
			f[i][j]=p1+p2-p3;
		}
		
		//move down
		if(i==n-k){
			continue;
		}
		
		ll upt=0,downt=0;
		
		int up=k-1;
		for(int j=i;j>=i-k+1;j--){
			upt+=getRS(j,k-1-up,k-1+up);
			up--;
		}
		
		int down=k-1;
		for(int j=i+1;j<=i+k;j++){
			downt+=getRS(j,k-1-down,k-1+down);
			down--;
		}
		
		dbg cout<<"F:"<<i+1<<" "<<k-1<<"="<<f[i][k-1]<<" "<<upt<<" "<<downt<<endl;
		
		
		f[i+1][k-1]=f[i][k-1]-upt+downt;	
		
	}
	
	int x=k-1,y=k-1;
	for(int i=k-1;i<=n-k;i++){
		for(int j=k-1;j<=m-k;j++){
			if(f[i][j]>f[x][y]){
				x=i;
				y=j;
			}
		}
	}
	
	cout<<x+1<<" "<<y+1<<endl;
	return 0;
}
 

Main.cpp: In function ‘int main(int, char**)’:
Main.cpp:268:117: warning: format ‘%d’ expects argument of type ‘int’, but argument 6 has type ‘long long int’ [-Wformat=]
     printf("(%d,%d) in dsu %d ind= %d sum_until=%d\t",i,j,dsuid[i][j],dsuind[i][j],ds<...>