https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c
解説
https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144292
難しい問題に直面したときは、まずは全探索ができないか考えてみよう。
何を全探索するかであるが、なるべく、それが決まれば他が全て決まるというものがふさわしい。
今回だと、M個から曲を2つ選べばシミュレートすることで全体の得点が分かるので、これを全探索しよう。
曲の選び方がM2通りくらいあって、それで歌ったときの得点をシミュレートするのにO(N)かかるので、
全体でO(NM2)で間に合う。
自分は実装で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; }