Cetate

#include <fstream>
using namespace std;
int n,m,w,a[550][550],pr[550],su[550];
long long sa[550][550],v[550];
struct grup{long long p1;int p2,p3,p4,p5;} sol;
void act(long long s1,int x1,int y1,int x2,int y2)
{
    if(sol.p1>s1) return;
    if(sol.p1==s1 && sol.p2<x1) return;
    if(sol.p1==s1 && sol.p2==x1 && sol.p3<y1) return;
    if(sol.p1==s1 && sol.p2==x1 && sol.p3==y1 && sol.p4<x2) return;
    if(sol.p1==s1 && sol.p2==x1 && sol.p3==y1 && sol.p4==x2 && sol.p5<=y2) return;
    sol.p1=s1,sol.p2=x1,sol.p3=y1,sol.p4=x2,sol.p5=y2;
}
int main()
{
    ifstream in("cetate.in");
    ofstream out("cetate.out");
    int t;
    in>>t>>n>>m>>w;
    sol.p1=-(1LL << 62);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            in>>a[i][j];
            sa[i][j]=a[i][j]+sa[i-1][j];

        }
    if(t==1)
    {
      for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            sa[i][j]=a[i][j]+sa[i-1][j]+sa[i][j-1]-sa[i-1][j-1];
      for(int i=w;i<=n;++i)
        for(int j=w;j<=m;++j)
            act(sa[i][j]-sa[i-w][j]-sa[i][j-w]+sa[i-w][j-w],i-w+1,j-w+1,i,j);
    }
    else
        {
        for (int i1=1;i1<=n;++i1) {
          for (int i2=i1;i2<=n && i2<i1+w;++i2)
          {
            for (int j=1;j<=m;++j)
                v[j]=sa[i2][j]-sa[i1-1][j]+v[j-1];
            for (int j=1;j<=m;++j)
            {
                if(j%w==0 || v[j]<v[pr[j-1]])
                    pr[j]=j;
                else
                    pr[j]=pr[j-1];
            }
            for (int j=m;j>=0; --j)
            {
                if(j==m || (j+1)%w==0 || v[j]<=v[su[j+1]])
                    su[j]=j;
                else
                    su[j]=su[j+1];
            }

            for (int j=1; j<=m; ++j)
            {
                if(j<w)
                {
                    act(v[j] - v[pr[j-1]],
                        i1, pr[j-1]+1, i2, j);
                    continue;
                }
                int left=max(0, j-w);
                int right=j-1;
                if(v[su[left]] <= v[pr[right]])
                    act(v[j]-v[su[left]],
                        i1, su[left]+1, i2, j);
                else
                    act(v[j]-v[pr[right]],
                        i1, pr[right]+1, i2, j);
            }
        }
    }

    }
    long long best_sum;
    int i1, i2, j1, j2;
    best_sum=sol.p1,i1=sol.p2,j1=sol.p3,i2=sol.p4,j2=sol.p5;
    out << best_sum << '\n';
    out << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n';

    return 0;
}