pastebin

Paste Search Dynamic
Recent pastes
count
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5.  
  6. int main() {
  7.     fastio();
  8.     int t=0;
  9.     cin>>t;
  10.     while(t--)
  11.     {
  12.         ll n,m,k,count=0;
  13.         cin>>n>>m>>k;
  14.         ll arr[n][m];
  15.         ll dp[n+1][m+1]={0};
  16.         memset(dp,0,sizeof(dp));
  17.         for(ll i=0;i<n;i++){
  18.             for(ll j=0;j<m;j++){
  19.                   cin>>arr[i][j];
  20.                   if(arr[i][j]>=k){
  21.                      count++;
  22.                   }  
  23.             }
  24.         }
  25.         if(count == n*m){
  26.  
  27.                 for(ll i=2; i<=n; i++){
  28.                     count += (n-i+1)*(m-i+1);
  29.                 }
  30.                 cout<<count<<"n";
  31.         } else if(count==0){
  32.             cout<<"0n";
  33.         } else {
  34.         for(ll i=1;i<n+1;i++){
  35.             for(ll j=1;j<m+1;j++){
  36.                 dp[i][j]=arr[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
  37.  
  38.             }
  39.         }
  40.         ll sum=0,p=0;
  41.         bool yes=false;
  42.         for(ll l=2;l<=n;l++){
  43.             yes=false;
  44.             for(ll i=1;i<n+1;i++){
  45.               yes=false;
  46.               for(ll j=1;j<m+1;j++){
  47.                 yes=false;
  48.                 if(i-l>=0 && j-l>=0){
  49.                    //cout<<i-l<<" "<<j-l<<"n";
  50.                    sum = dp[i][j]-dp[i-l][j]-dp[i][j-l]+dp[i-l][j-l];
  51.                   // cout<<l<<" "<<sum<<"n";
  52.                    if((dp[i][m]-dp[i-l][m]-dp[i][m-l]+dp[i-l][m-l])<k*(l*l)){
  53.                        break;
  54.                    }
  55.                    else if(sum/(l*l) >=k && j==1){
  56.                        count+=(n-i+1)*(m-j+1);
  57.                       // cout<<n-i+1
  58.                        yes=true;
  59.                        break;
  60.                    } else if(sum/(l*l)>=k && j!=1 ){
  61.                        count+=m-j+1;
  62.                        break;
  63.                    } else {
  64.                        continue;
  65.                    }
  66.                    yes=false;
  67.                    p=0;
  68.                 } else if(i-l<0) {
  69.                     break;
  70.                 }
  71.               }
  72.               if(yes){
  73.                   break;
  74.               }
  75.           }
  76.         }
  77.         cout<<count<<"n";
  78.       }  
  79.  
  80.  
  81.     }
  82.     return 0;
  83. }
Parsed in 0.017 seconds