PCK2012 問5

問題みてよく分からず、DPで解くのか？PCKだし全探索か？みたいなことを考えつつ結局放置していた。
パソコン甲子園2012予選 - 自分の解法 - kyuridenamidaのチラ裏
貪欲法？
普通に考えてみればパイプの長さの総和はジョイントの位置によらないじゃん。どう考えても短いジョイント外すのが最善じゃん。
なんで気が付かなかったんや……

ここまで分かれば書くだけ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
  int n,ibuf,ans;
  while(cin >> n, n){
    vector<int> j;
    int sum = 0;
    for(int i = 0; i < n; i++){
      cin >> ibuf;
      sum += ibuf;
    }
    for(int i = 0; i < n - 1; i++){
      cin >> ibuf;
      j.push_back(ibuf);
      sum += ibuf;
    }

    sort(j.begin(), j.end());

    ans = sum;

    for(int i = 2; i < n + 1; i++){
      sum = sum - j[i - 2];
      if(ans < sum * i)
        ans = sum * i;
      else
        break;
    }

    cout << ans << endl;
  }
  return 0;
}

正直コレと問3は普通に取れてておかしくない問題だった。もうちょっと事前にリハビリしとけば……