カラオケ [パ研合宿2019 第3日「パ研杯2019」 C]

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

解説

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144292

難しい問題に直面したときは、まずは全探索ができないか考えてみよう。
何を全探索するかであるが、なるべく、それが決まれば他が全て決まるというものがふさわしい。
今回だと、M個から曲を2つ選べばシミュレートすることで全体の得点が分かるので、これを全探索しよう。

曲の選び方がM²通りくらいあって、それで歌ったときの得点をシミュレートするのにO(N)かかるので、
全体でO(NM²)で間に合う。
自分は実装でchmaxというマクロを使っている。
chmax(a, b)と書くと、a=max(a,b)と同様の働きをする。
参照渡しで関数に与えているので更新ができるということ。

int N, M, A[101][101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) rep(j, 0, M) cin >> A[i][j];

    ll ans = 0;
    rep(t1, 0, M) rep(t2, t1 + 1, M) {
        ll tot = 0;
        rep(i, 0, N) tot += max(A[i][t1], A[i][t2]);
        chmax(ans, tot);
    }
    cout << ans << endl;
}