UVA 11951- Area ( dp, Two Pointers )

UVA 11951-Area ( dp, Two Pointers )

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digits    0123456789012345678 ///
#define MX     102
#define inf    100000001000000LL
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int n,m;
ll K,dp[MX][MX];
int main() {
    int tc,cs=1,i,j,k,x;
    S(tc);
    while(tc--){
        S2(n,m);
        SL(K);
        for(i=1;i<=n;i++){
            dp[i][0]=0;
            for(j=1;j<=m;j++){
                S(x);
                dp[i][j]=dp[i][j-1]+x; ///row-wise sum
            }
        }
        ll MxArea=0LL;/// Max Area;
        ll MnCst=inf; ///Min Cost of max area
        for(i=1;i<=m;i++){ ///first column
            for(j=i;j<=m;j++){ ///second column
                ll sm=0; /// for SUM;
                int kk=1;/// second pointer for column;
                for(k=1;k<=n;k++){ ///first pointer for column
                    sm+=dp[k][j]-dp[k][i-1];
                    while( sm>K && kk<=k ){
                        sm-=( dp[ kk ][ j ]-dp[ kk][i-1] );
                        kk++;
                    }
                    ll area=(ll)(k-kk+1)*(ll)(j-i+1);
                    if( area==MxArea )MnCst=min(MnCst,sm);
                    else if(area>MxArea){
                         MxArea=area;
                         MnCst=sm;
                    }
                }
            }
        }
        printf("Case #%d: %lld %lld\n",cs++,MxArea,MnCst);
    }
    return 0;
}