Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-29

SRM383 Div1 Easy: Planks

| 23:55 | SRM383 Div1 Easy: Planks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM383 Div1 Easy: Planks - naoya_t@topcoder SRM383 Div1 Easy: Planks - naoya_t@topcoder のブックマークコメント

Plankとは厚い板のこと。

vector<int>のなかから最大値を取るのに *max_element(all(lengths)) を使ってるけど、lengths.max()みたいなのって出来ないかな・・・

それにしてもサンプルケースが親切!

class Planks {
 public:
  int makeSimilar(vector<int> lengths, int costPerCut, int woodValue) {
    int n=sz(lengths); //1-50; 1-10000 each
    int maxl=*max_element(all(lengths)); // max length
    int maxa=0; // max amount
    for(int u=1;u<=maxl;u++){
      int cost=0, value=0;
      rep(i,n){
        int li=lengths[i];
        int k=li/u, r=li%u, cut=r>0?k:(k-1);
        int c=costPerCut*cut, v=k*u*woodValue;
        if (c<v) {
          cost+=c; value+=v;
        }
      }
      int a=value-cost;
      maxa=max(a,maxa);
    }
    return maxa;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20081229