Codeforces ラウンド #132 (ディビジョン 2) D. Hot Days_html/css_WEB-ITnose

D. 暑い日

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

ベルラントの公式首都と文化首都は、n つの地域を通る 1 本の道路で結ばれています。各地域には独自の気候があるため、i 番目 (1?≤?i?≤?n) 番目の地域は、夏の気温が ti 度で安定しています。

この夏、m 人の学童のグループが首都からの旅行を希望しています。博物館や観光スポットを訪れるために文化の中心地へ。旅行の主催者は子供たちをバスで都市間を移動させますが、非常に暑い場合もあります。具体的には、バスが i 番目の地域を走行していて、k 人の小学生が乗っている場合、バス内の温度は ti?+?k 度になります。

もちろん、バスが暑いのが好きな人はいません。したがって、バスが i 番目の地域を走行するとき、車内の気温が Ti 度を超えている場合、バスに乗っている学童はそれぞれ、不快な状況に対する補償を要求します。補償金は xi ルーブルと同額で、バス内の温度が制限を超えた地域ごとに請求されます。

費用を節約するために、旅行の主催者は旅行の開始時に追加のバスを任意に追加または削除する場合があります。そしてリージョン間（もちろん、どのリージョンを通過するにも少なくとも 1 台のバスが必要です）。主催者は子供たちを任意にバスに振り分けることもできますが、i 番目の地域の各バスの料金は主催者の負担となります。子どもたちをバスに振り分けるのにはお金はかかりません。

あなたの仕事は、主催者がすべての学童を輸送するために費やさなければならない最小ルーブル数を見つけることです。

入力

最初の入力行には 2 つの整数が含まれています。 n および m (1?≤?n?≤?105; 1?≤?m?≤?106) ?途中の地域の数とグループ内の児童の数もそれに応じて変わります。次の n 行にはそれぞれ 4 つの整数が含まれます。i 番目の行には ti、Ti、xi、costi (1?≤?ti,?Ti,?xi,?costi?≤?106) が含まれます。行内の数字は単一のスペースで区切られています。

出力

唯一の整数を出力します。すべての学童を輸送するために主催者が費やさなければならない最小ルーブル数です。

С++ で 64 ビット整数の読み取りまたは書き込みに %lld 指定子を使用しないでください。 cin、cout ストリーム、または %I64dspecifier を使用することをお勧めします。

サンプル テスト

入力

2 1030 35 1 10020 35 10 10

出力

120

入力

3 10010 30 1000 15 10 1000 310 40 1000 100000

出力

200065

注

最初のサンプルでは、​​主催者は最初の地域を移動するために 1 台のバスのみを使用します。ただし、バス内の気温は 30?+?10?=?40 度となり、10 人の小学生がそれぞれ賠償を請求することになります。 2 番目の地域でもグループを輸送するバスは 1 台だけですが、車内の温度は制限値を超えることはありません。全体として、主催者は 100?+?10?+?10?=?120 ルーブルを費やします。同様に、ｔ、Ｔ、ｘ、コストはそれぞれ、その領域の温度ｔ、車両内の最大温度限界Ｔ、車両内の温度がＴを超えた場合の各ユニットのコストｘ、車両のコスト、最小コストを求める。

思路：1. 当 m <= (T-t) 时
最后的费用都为 ： cost
2.m>(T-t) 时
有两种选择 一个是尽量做在一辆车上（对于补助费比较少时）
sum=m*x;
另一个是 尽量多做车，但是要保证车都坐满（刚好达到不要补助费的时候）。 
sum=cost*( m%(T-t)==0? m/(T-t)+1: m/(T-t) );

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6typedef long long ll;using namespace std;int main(){    __int64 n,m;    while (~scanf("%I64d%I64d",&n,&m))    {        __int64 t,T,x,c,ss1,ss2;        __int64 ans=0;        __int64 s1,s2;        for (__int64 i=0;i<n;i++)        {            s1=INF,s2;            scanf("%I64d%I64d%I64d%I64d",&t,&T,&x,&c);            if(T-t<=0)            {                ans+=m*x+c;                continue;            }            if (m<=T-t)            {                ans+=c;                continue;            }            ss1=c+m*x;            ss2=c*(m%(T-t)==0?m/(T-t):(m/(T-t)+1));            ans+=min(ss1,ss2);        }        printf("%I64d\n",ans);    }    return 0;}/*2 1030 35 1 10020 35 10 103 10010 30 1000 15 10 1000 310 40 1000 100000*/