与えられた \(N\) 個のマスの \(x\) 座標・\(y\) 座標として現れない値をあえて \(R\) や \(C\) として選ぶことで解が良くなることは無いため、座標圧縮によって \(N\) 行 \(N\) 列(あるいは \(N\) に満たない行数・列数)のマス目上の問題とみなせます。

\((R,C)\) に対する \(S\) は「( \(R\) 行目に書かれた整数の総和) \(+\) (\(C\) 列目に書かれた整数の総和) \(- (R,C)\) に書かれた整数」です。これを念頭に \(R\) を全探索します。\(C\) は基本的に \(C\) 列目に含まれる値の総和が最大となるようなものを選べば良いです。特に、\((R,C)\) が入力に含まれない場合は \(C\) 列目に含まれる値が最大でない列を選んでも \(S\) が大きくなりません。\((R,C)\) が入力に含まれる場合はこの限りではないので \(2\) 番目に大きいものを見る必要があり、それについても \((R,C)\) が入力に含まれるならば \(3\) 番目に大きいものを見る必要があり、\(\ldots\) と続きます。しかし、やはり \((R,C)\) が含まれなかった場合はより \(C\) 行目の総和が小さいような \(C\) において \(S\) が大きくなることはあり得ないため、その時点で処理を打ち切れます。そして、打ち切られるまでの回数は \(R=1,2,\ldots,N\) 全体で \(\mathrm{O}(N)\) 回となるため、上記方法によって十分高速に解を求めることが出来ます。