记录编号	586899	评测结果	AAWWWWWWWW
题目名称	1162.[POJ 1180]任务安排2	最终得分	20
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	0.442 s
提交时间	2024-03-04 17:08:00	内存使用	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] + s * (c[n] - c[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++){
        while(l < r && slope(q[l],q[l+1]) <= t[i])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 && slope(q[r-1],q[r]) >= slope(q[r],i))r--;
        q[++r] = i;
    }
    printf("%lld\n",f[n]);

	return 0;

}