TopCoder SRM 383 Div1 Easy Planks

問題

n本の木の棒がある。それぞれの長さはlengths[i]である。
ここから木の棒を切り出して売りたい。
売る木の棒の長さは整数で、かつ全ての長さが等しくなければならない。

木の切断には一回ごとにcostPerCutの値段がかかる。
長さlの木の棒はl*woodValueの値段で売れる。
余った分は全て捨てる。

最大でいくらの利益を得ることができるか、求めよ。

制約条件

n≦50
lengths[i]≦10000
costPerCut,woodValue≦1000

方針

切り出す棒の長さを1〜10000の全てを試す。
長さを決めたら、それぞれの棒から売る棒が何本取れるのかが分かるので、
切り出せるだけ切り出す。

赤字になる場合は切らないようにする。

ソースコード

class Planks {
  public:
  int makeSimilar(vector <int> lengths, int costPerCut, int woodValue) {
    int ans=0;
    for(int l=1;l<=10000;l++){
      int tmp=0;
      rep(i,lengths.size()){
        int c=(lengths[i]+l-1)/l-1;
        tmp+=max(0,woodValue*(c+(lengths[i]%l==0))*l-c*costPerCut);
      }
      ans=max(ans,tmp);
    }
    return ans;
  }
};