【AtCoder】ABC 388 B - Heavy Snake | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 30

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 匹のヘビがおり、 $i$ 匹目のヘビの太さは $T_i$ 、長さは $L_i$ である。

ヘビの重さを太さと長さの積とするとき、 $1 \leq k \leq D$ を満たす各整数 $k$ について、すべてのヘビの長さが $k$ 伸びたときの最も重いヘビの重さを求めよ。

制約

$1 \leq N, D \leq 100$
$1 \leq T_i, L_i \leq 100$
入力はすべて整数。

考察

$i$ 匹目のヘビの重さは $T_i (L_i + k)$ と書くことができるので、各 $k$ について $\underset{1 \leq i \leq N}{\max} T_i (L_i + k)$ を求めればよい。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N, D;
    cin >> N >> D;
    vector<int> T(N), L(N);
    rep(i, 0, N) cin >> T[i] >> L[i];

    repe(k, 1, D)
    {
        int ans = 0;
        rep(i, 0, N) chmax(ans, T[i] * (L[i] + k));

        cout << ans << endl;
    }

    return 0;
}