https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_b
解説
https://atcoder.jp/contests/hitachi2020/submissions/10691153
- クーポンを使わずに冷蔵庫と電子レンジをそろえる
- クーポンを使って、冷蔵庫と電子レンジをそろえる
の2択がまずある。
選択1については、どちらも最安のものを買えば、全体が最安となる。
つまりこっちはO(AB)見る必要はなく、最小を探すだけでO(A+B)
選択2については、各クーポンについて必要な値段を計算すればいいので、O(M)
この最小値をとればいいため、全体O(A+B+M)で解ける。
int A, B, M; int a[101010], b[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B >> M; rep(i, 0, A) cin >> a[i]; rep(i, 0, B) cin >> b[i]; int mi_a = inf; rep(i, 0, A) chmin(mi_a, a[i]); int mi_b = inf; rep(i, 0, B) chmin(mi_b, b[i]); int ans = mi_a + mi_b; rep(i, 0, M) { int x, y, c; cin >> x >> y >> c; y--; x--; chmin(ans, a[x] + b[y] - c); } cout << ans << endl; }