Take the the row or column (without loss of generality, a row) with the minimum possible sum $ S$ of its elements. Let $ z$ be the number of zeros in this row. We will assume $ S < \frac{n}{2}$ once the other case is obvious. Clearly $ S \ge n - z \Rightarrow z \ge n - S$. The total sum $ T$ of all elements of the matrix is at least the number of zeros in this row multiplicated by $ n - S$ (because the sum of the elements of a row and a column meeting in a zero is $ \ge n$) plus the number of nonzero elements times $ S$ (that is the minimum possible sum), it is, \[ z(n - S) + (n - z)S.\] Note that, being $ z \ge n - S$ and $ n - S \ge S$, we can put $ z - 1$ instead of $ z$ and $ n - z + 1$ instead of $ n - z$ until we get $ z = n - S$, what makes the sum become smaller. So we have \[ T \ge (n - S)^2 + S^2 \ge 2(\frac{n - S + S}{2})^2 = \frac{n^2}{2}\] by AM - QM inequality.

If the main diagonal contains all zeroes, we can immediately deduce from the condition that the sum $S$ of the elements is at least $n^2/2$. This motivates us to consider the largest possible subset of elements, all zero, which are pairwise in different rows of columns - let the size of this subset be $k$. (If there is no such subset, $S\ge n^2$.) Since the condition is invariant under the operation of switching rows or columns, we may rearrange the matrix such that these $k$ entries are on the main diagonal of the matrix, i.e. $a_{11}=a_{22}=\dots=a_{kk}=0$. Let $X=\sum_{1\le i,j\le k}a_{ij}$, $Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij}$ and $Z=\sum_{k<i,j\le n}a_{ij}$. Then applying the condition to $a_{11},\dots,a_{kk}$, we get $2X+Y\ge kn$. If $i\le k<j$, then if $a_{ij}=a_{ji}=0$, then we may toss $a_{ii}$ out of our set and replace it with $a_{ij}$ and $a_{ji}$, to form a larger feasible set of elements, contradiction. Consequently, $a_{ij}+a_{ji}\ge 1$ for $i\le k<j$, which upon summation yields $Y\ge k(n-k)$. Finally, $Z\ge (n-k)^2$, trivially. Therefore, $$2S=2(X+Y+Z)\ge 2X+Y+Y+Z\ge kn+k(n-k)+(n-k)^2=k^2+2k(n-k)+(n-k)^2=n^2.$$

Denote $\ell_i,c_i$ the $i$th line and column and $s(\ell_i), s(c_i)$ the sum of the elements on that row. Let $M=\max_{\sigma \in S_n} | \{ 1\le i\le n| a_{i\sigma(i)}=0\} |$. For each permutation $\sigma\in S_n$, assign to it the number $$\displaystyle\sum\limits_{a_{i\sigma(i)=0}} \left ( s(\ell_i)+s(c_{\sigma(i)}) \right )$$Now pick a permutation $\sigma$ such that it generates $M$ and its assigned number is minimal. Suppose wlog that $\{ 1\le i\le n| a_{i\sigma(i)}=0\}=\{1,2,..,k\}$. If $k=n$, we are done as twice the sum of all elements is $$\displaystyle\sum\limits_{i=1}^{n} s(\ell_i) +\displaystyle\sum\limits_{i=1}^{n} s(c_i)=\displaystyle\sum\limits_{i=1}^{n} (s(\ell_i)+s(c_{\sigma(i)}))\ge n^2$$ So suppose $k<n$ and look at a $j$ such that $k+1\le j\le n$. By the maximality of $M$, $\ell_j$ can have $0$ only on the columns $\sigma(1),...,\sigma(k)$. Note that if $\ell_j$ has a $0$ on $c_{\sigma(r)}$ with $r\le k$, i.e. $a_{j\sigma(r)}=0$, by the minimality of the assigned number of $\sigma$, we have that $s(\ell_j)\ge s(\ell_r)$. However, if the column $c_{\sigma(j)}$ has a $0$ on $\ell_r$, i.e. $a_{r\sigma(j)}=0$, by the same argument we have $s(c_\sigma(j))\ge s(c_\sigma(r))$, hence $s(\ell_j)+s(c_{\sigma(j)})\ge s(r)+s(c_{\sigma(r)})\ge n$. Suppose that $0$ appears exactly $t$ times on $\ell_j$. This means that $s(\ell_j)\ge n-t$. Suppose that the $0$s of $\ell_j$ appear on the columns $c_{\sigma(i_1)},...,c_{\sigma(i_t)}$. We have seen earlier that if $c_\sigma(j)$ has a $0$ on $i_1,..,i_t$ we have that $s(\ell_j)+s(c_{\sigma(j)})\ge n$. So suppose that it doesn't have $0$ on these lines. However, $c_{\sigma(j)}$ has $0$s only on the lines $\ell_1,..,\ell_k$ by the maximality of $M$, hence $c_{\sigma(j)}$ has at most $k-t$ zeroes, so $s(c_{\sigma(j)})\ge n-k+t$. We thus infer that $$s(\ell_j)+s(c_{\sigma(j)})\ge (n-t)+(n-k+t)=2n-k\ge n$$so $s(\ell_j)+s(c_{\sigma(j)})\ge n,\ \forall j\ge k+1$. By the hypothesis this is also true for $j\le k$ so summing over all values of $j$ we get that the sum is at least $\dfrac{n^2}{2}$.

Old Classics : Let $p$ denote the smallest sum a row or column can have in the array. WLOG, assume that it's the first row. If $p \ge \frac{n}{2}$ then we are done. Else, let $r$ denote the number of non-zeros in the first row. WLOG, let the first $r$ elements of the row be non-zeros. Then, the last $n-r$ columns have a sum of at-least: $(n-r)(n-p)$ and first $r$ columns have sum of at-least $pr$. Thus, the sum of elements in the matrix is at-least: $$(n-r)(n-p)+pr \ge \frac{n^2}{2}$$since $\frac{n}{2} \ge p \ge r$.