2036: [Blue Bridge Cup 2022 preliminary] statistical submatrix (two-dimensional prefix sum, one-dimensional prefix sum)

2036: [ Blue Bridge Cup 2022 Preliminaries ] Statistical submatrix

Memory limit ：256 MB The time limit ：1 S Standard input and output

Topic type ： Tradition Evaluation method ： Text comparison Uploaded by ： External import

Submit ：310 adopt ：74

Title Description

Given a N × M Matrix A, Please count how many sub matrices there are ( Minimum 1 × 1, Maximum  N × M) Satisfy ：
The sum of all numbers in the submatrix does not exceed the given integer K?

Input format

The first line contains three integers N, M and K.
after N Each line contains M It's an integer , Representative matrix A.
30% Test data for ：1≤N,M≤20;
70% Test data for ：1≤N,M≤100;
100% Test data for ：1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000.

Output format

An integer represents the answer .

sample input Copy

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

sample output Copy

19

Data range and tips

The submatrix satisfying the condition has 19, contain ：
The size is 1 × 1 There are 10 individual .
The size is 1 × 2 There are 3 individual .
The size is 1 × 3 There are 2 individual .
The size is 1 × 4 There are 1 individual .
The size is 2 × 1 There are 3 individual .

 

The irony is , The first time I saw this question , Write a six level cycle , Scared to death ！

For this two-dimensional matrix , Sum up , It can be used dp[i][j] To express matr[0][0] To matr[i][j] And ,
   This will simplify the following steps of summation , Reduce the time complexity of two levels , This is the two-dimensional prefix and .

   meanwhile , How to express one-dimensional prefix and ?dp[i][j] Express matr[0][j] To matr[i][j] And , This only means
   The first j Ahead of the line i Rows and . So this is the difference between one-dimensional prefix and two digit prefix

/** For this two-dimensional matrix , Sum up , It can be used dp[i][j] To express matr[0][0] To matr[i][j] And ,
    This will simplify the following steps of summation , Reduce the time complexity of two levels , This is the two-dimensional prefix and .

    meanwhile , How to express one-dimensional prefix and ?dp[i][j] Express matr[0][j] To matr[i][j] And , This only means 
    The first j Ahead of the line i Rows and . So this is the difference between one-dimensional prefix and two digit prefix 
*/


/** Two dimensional prefix and solution */
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[502][502]={0};
int main()
{
    memset(dp,0,sizeof(dp));
    int n,m,top;
    scanf("%d%d%d",&n,&m,&top);
    int val;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&val);
            dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+val;
        };
    long long sum=0;    //sum It must also be defined as long long, Otherwise, 20% of the answer is wrong 
//    for(int i=1;i<=n;++i)     // The quadruple cycle obviously timed out , Baidu saw " Double pointer solution "
//    {
//        for(int j=1;j<=m;++j)
//        {
//            for(int k=i;k<=n;++k)
//            {
//                for(int h=j;h<=m;++h)
//                {
//                    if(dp[k][h]-dp[k][j-1]-dp[i-1][h]+dp[i-1][j-1]<=top)
//                        sum+=1;
//                    else break;
//                }
//            }
//        }
//    }

    for(int i=1;i<=n;++i)   // Baidu saw " Double pointer solution "
        for(int j=i;j<=n;++j)   /** Now I can see , Namely tow point*/
            for(int col_l=1,col_r=1;col_r<=m;++col_r)
            {
                while(col_l<=col_r&&(dp[j][col_r]-dp[j][col_l-1]-dp[i-1][col_r]+dp[i-1][col_l-1])>top)
                    ++col_l;
                if(col_l<=col_r)
                    sum+=col_r-col_l+1;
            }
    cout << sum << endl;
    return 0;
}

/** One dimensional prefix and solution */

/** One dimensional prefix and solution */
/**
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[502][502]={0};
int main()
{
    memset(dp,0,sizeof(dp));
    int n,m,top;
    scanf("%d%d%d",&n,&m,&top);
    int val;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&dp[i][j]);
            dp[i][j]+=dp[i-1][j];
        };
    long long result=0;    //result It must also be defined as long long, Otherwise, 20% of the answer is wrong 

    for(int i=1;i<=n;++i)   // Baidu saw " Double pointer solution "
        for(int j=i;j<=n;++j)   // Now I can see , Namely tow point
            for(int col_l=1,col_r=1,sum=0;col_r<=m;++col_r)
            {
                sum+=dp[j][col_r]-dp[i-1][col_r];
                while(sum>top)
                {
                    sum-=dp[j][col_l]-dp[i-1][col_l];
                    ++col_l;
                }

                if(col_l<=col_r)
                    result+=col_r-col_l+1;
            }
    cout << result << endl;
    return 0;
}
*/