Maximum Score [CodeChef January Challenge 2018 B]

https://www.codechef.com/JAN18/problems/MAXSC

N*N要素の行列Aがある。
各行から数を1つずつ選んで数列Eを作る。
数列Eを狭義単調増加するように選ぶとき、数列Eの総和の最大値は何か。
もし、狭義単調増加するように取れないなら-1を出力する。

解法

貪欲に計算できる。
数列Eを後ろから確定していく。
狭義単調増加させるにも、数列Eの総和を最大化するにも、後ろから取っていく場合はなるべく大きな数を取るほうがお得である。
そのため、後ろから順に取っていって、今まで確定した数よりも小さい数の中で最大のものを順次取る。
もし、取れるものがなくなったら、構築は無理なので-1

typedef long long ll;
#define INF 1LL<<60
int N;
ll A[707][707];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    rep(y, 0, N) rep(x, 0, N) cin >> A[y][x];
    
    ll ans = 0;
    ll ma = INF;
    rrep(y, N - 1, 0) {
        ll nxt = -1;
        rep(x, 0, N) if (A[y][x] < ma) nxt = max(nxt, A[y][x]);
        if (nxt < 0) {
            printf("-1\n");
            return;
        }
        ans += nxt;
        ma = nxt;
    }
    printf("%lld\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}