naoya_t@topcoder

SRM383 Div1 Easy: Planks

過去問, 練習 | 23:55 |

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;
  }
};