Dm @txa16 for any Offcampus Oncampus exam interview help

For question check question bank : @quesbank1🏦

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Solution {

    static class Dinic {
        int n;
        int[] head, to, next, level, it, q;
        long[] cap;
        int edgeCnt = 0;

        Dinic(int n, int maxEdges) {
            this.n = n;
            head = new int[n];
            Arrays.fill(head, -1);
            to = new int[maxEdges];
            next = new int[maxEdges];
            cap = new long[maxEdges];
            level = new int[n];
            it = new int[n];
            q = new int[n];
        }

        void addEdge(int u, int v, long c) {
            to[edgeCnt] = v;
            cap[edgeCnt] = c;
            next[edgeCnt] = head[u];
            head[u] = edgeCnt++;

            to[edgeCnt] = u;
            cap[edgeCnt] = 0;
            next[edgeCnt] = head[v];
            head[v] = edgeCnt++;
        }

        boolean bfs(int s, int t) {
            Arrays.fill(level, -1);
            int qs = 0, qe = 0;
            level[s] = 0;
            q[qe++] = s;

            while (qs < qe) {
                int v = q[qs++];
                for (int e = head[v]; e != -1; e = next[e]) {
                    int u = to[e];
                    if (cap[e] > 0 && level[u] == -1) {
                        level[u] = level[v] + 1;
                        q[qe++] = u;
                    }
                }
            }
            return level[t] != -1;
        }

        long dfs(int v, int t, long pushed) {
            if (pushed == 0) return 0;
            if (v == t) return pushed;

            for (int e = it[v]; e != -1; it[v] = e = next[e]) {
                int u = to[e];
                if (cap[e] > 0 && level[u] == level[v] + 1) {
                    long tr = dfs(u, t, Math.min(pushed, cap[e]));
                    if (tr > 0) {
                        cap[e] -= tr;
                        cap[e ^ 1] += tr;
                        return tr;
                    }
                }
            }
            return 0;
        }

        long maxFlow(int s, int t) {
            long flow = 0;
            long INF = Long.MAX_VALUE / 4;

            while (bfs(s, t)) {
                System.arraycopy(head, 0, it, 0, n);
                while (true) {
                    long pushed = dfs(s, t, INF);
                    if (pushed == 0) break;
                    flow += pushed;
                }
            }
            return flow;
        }
    }

    public static int c(int N, int M, List<Long> A, List<Long> B) {
        int V = N + M + 2;
        int s = 0;
        int t = V - 1;

        int maxEdges = 2 * (N * M + N + M) + 5;
        Dinic dinic = new Dinic(V, maxEdges);

        for (int i = 0; i < N; i++) dinic.addEdge(s, 1 + i, A.get(i));
        for (int j = 0; j < M; j++) dinic.addEdge(1 + N + j, t, B.get(j));

        for (int i = 0; i < N; i++) {
            int u = 1 + i;
            long ii = (long) (i + 1);
            for (int j = 0; j < M; j++) {
                int v = 1 + N + j;
                long cap = ii * (long) (j + 1);
                dinic.addEdge(u, v, cap);
            }
        }

        long ans = dinic.maxFlow(s, t);
        return (int) ans;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = Integer.parseInt(scan.nextLine().trim());
        int M = Integer.parseInt(scan.nextLine().trim());

        List<Long> A = new ArrayList<>(N);
        for (int j = 0; j < N; j++) A.add(Long.parseLong(scan.nextLine().trim()));

        List<Long> B = new ArrayList<>(M);
        for (int j = 0; j < M; j++) B.add(Long.parseLong(scan.nextLine().trim()));

        int result = c(N, M, A, B);
        System.out.println(result);
    }
}

Make Resume this type more ATS friendly Resume