记录编号	586902	评测结果	AAAAAAAAAA
题目名称	1162.[POJ 1180]任务安排2	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.446 s
提交时间	2024-03-04 17:23:50	内存使用	11.00 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5+10;
const ll inf = 1e17;
int n,l,r,q[N];
ll s,f[N],t[N],c[N];
ll X(int a){return c[a];}
ll Y(int a){return f[a];}
double slope(int a,int b){
    if(X(a) == X(b))return -inf;
    return double(Y(a) - Y(b)) / (X(a) - X(b));
}
int main(){
	freopen("poj1180_batch.in","r",stdin);
    freopen("poj1180_batch.out","w",stdout);
    scanf("%d%lld",&n,&s);
    for(int i = 1;i <= n;i++)scanf("%lld%lld",&t[i],&c[i]),t[i] += t[i-1],c[i] += c[i-1];
    l = r = 1,q[1] = 0;
    for(int i = 1;i <= n;i++){
        f[i] = inf;
        while(l < r && (Y(q[l+1]) - Y(q[l])) <= (s+t[i]) * (X(q[l+1]) - X(q[l])))l++;
        if(l <= r){
            int j = q[l];
            f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
        }
        while(l < r && (Y(q[r]) - Y(q[r-1])) * (X(i) - X(q[r])) >= (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r-1])))r--;
        q[++r] = i;
    }
    printf("%lld\n",f[n]);

	return 0;

}