CODE K, C++ (gcc) - rextester

CODE K

//-------------------------------------------------------------------------------------------------------------------------------
//g++  7.4.0 
//Base File           
//-------------------------------------------------------------------------------------------------------------------------------
/*                                                 ᕙ(  • ‿ •  )ᕗ Dire Wolf
                                              
                                                     ->Manan's Code Pad<-
                                            
Patience                                                                                                                  Bravery
                                                           
*/
//-------------------------------------------------------------------------------------------------------------------------------
//                                                     ¯\_(ツ)_/¯ <Code>
//-------------------------------------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

int main()
{
    //std::cout << "Hello, world!\n";
      
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        int a[n][m]={0};
        int count=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                cin>>a[i][j];
                if(a[i][j]>=k)
                    count++;
            }
        }
       
        vector<vector<int>>dp(n+1,vector<int>(m+1, 0));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i-1][j-1];
            }
        }
          /*for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
               cout<<dp[i][j]<<" ";
            }
              cout<<endl;
        }*/
        
        for(int i=2; i<=n; i++)
        {
            for(int row=1; row<=n-i+1; row++)
            {
                int left=-1;
                int l=1;
                int r=m-i+1;
                while(l<r)
                {
                    int mid=(l+r)/2;
                    int s1=row;
                    int s2=mid;
                    int e1=s1+i-1;
                    int e2=s2+i-1;
                    int sum=dp[e1][e2]-dp[e1][s2-1]-dp[s1-1][e2]+dp[s1-1][s2-1];
                    
                    //cout<<av;
                    if(sum>=k*i*i)
                    {
                        left=mid;
                        r=mid-1;
                    }
                    else
                    {
                        l=mid+1;
                    }
                }
                
                cout<<left<<" ";
                if(left>0)
                {count+=m-i+2-left;}
        }
          
        }
      
        cout<<count<<endl;
        
        
    }
      return 0;
}

//-------------------------------------------------------------------------------------------------------------------------------
//                                                          End
//-------------------------------------------------------------------------------------------------------------------------------


run \| edit \| history \| help	0