In this HackerEarth Plus Plus problem solution, You are given a two-dimensional grid A of size n x m (n rows and m columns). Your task is to select two nonoverlapping Plus signs from the grid and do multiplication with corresponding elements and find out summation. What is the maximum summation?


HackerEarth Plus Plus problem solution


HackerEarth Plus Plus problem solution.

#include<bits/stdc++.h>
#define PI acos(-1.0)
#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;
typedef unsigned long long ull;
int dx[]= {0,1,0,-1,0};
int dy[]= {0,0,1,0,-1};
#define MX     55
#define inf    100000001LL
#define MD     1006000007LL
#define eps    1e-9

int ar[MX][MX];
int vis[MX][MX];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ar[i][j];
        }
    }
    int xa,ya,xb,yb;
    int mx=0;
    for(int i=2;i<=n-1;i++){
        for(int j=2;j<=m-1;j++){

            for(int k=0;k<5;k++){
                int nx=i+dx[k];
                int ny=j+dy[k];

                vis[ nx ][ ny ]=1;

            }
            for(int a=2;a<=n-1;a++){
                for(int b=2;b<=m-1;b++){
                    bool ok=true;
                    int ans=0;
                    for(int k=0;k<5;k++){
                        int nx=a+dx[k];
                        int ny=b+dy[k];
                        ans+=( ar[nx][ny]*ar[ i+dx[k] ][ j+dy[k] ] );
                        if( vis[nx][ny] ) {
                            ok=false;
                            break;
                        }
                    }
                    if(ok){
                        if( ans>mx ){
                            mx=ans;
                            xa=i,ya=j;
                            xb=a,yb=b;
                        }
                    }
                }
            }
        }
    }

    cout<<mx<<endl;

    return 0;
}


Second solution

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        PlusPlus solver = new PlusPlus();
        solver.solve(1, in, out);
        out.close();
    }

    static class PlusPlus {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int m = in.scanInt();
            int ar[][] = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if ((ar[i][j] = in.scanInt()) >= 10) throw new RuntimeException();
            if (n < 6 || n > 50 || m < 6 || m > 50) throw new RuntimeException();
            int ans = 0;
            for (int i = 1; i < n - 1; i++)
                for (int j = 1; j < m - 1; j++)
                    for (int k = 1; k < n - 1; k++)
                        for (int l = 1; l < m - 1; l++)
                            if (Math.abs(i - k) + Math.abs(j - l) > 2)
                                ans = Math.max(ans, (ar[i][j] * ar[k][l]) + (ar[i][j - 1] * ar[k][l - 1]) + (ar[i - 1][j] * ar[k - 1][l]) + (ar[i + 1][j] * ar[k + 1][l]) + (ar[i][j + 1] * ar[k][l + 1]));


            out.println(ans);
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}