[AOJ] No. 0260 パイプつなぎ職人の給料

2020年1月18日2020年12月15日

問題

方針

ジョイントの使う順番は給料に影響を与えないので、ジョイントを使うときは最大のものから使うべきです。したがって、ジョイントを降順に並べ、全探索を行います。ジョイントを使う度にパイプの本数が減る一方で、ジョイント分の長さが加算されます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    while (n != 0) {
        vector<ll> p(n), j(n - 1);
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            sum += p[i];
        }
        for (int i = 0; i < n - 1; i++) {
            cin >> j[i];
        }
        ll ans = n * sum;
        sort(j.begin(), j.end(), greater<int>());
        for (int i = 0; i < n - 1; i++) {
            sum += j[i];
            ans = max(ans, (n - i - 1) * sum);
        }
        cout << ans << "\n";
        cin >> n;
    }
    return 0;
}