救救孩子,,全WA ,
查看原帖
救救孩子,,全WA ,
122794
tuya_楼主2021/3/13 15:07

已经化除为乘,还是全WA

救救孩子,,

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define ll long long
const int maxn = 300010;
ll n,s;
ll t[maxn],c[maxn],f[maxn],q[maxn];
int he,ta;

ll X(int i){return c[i];}
ll Y(int j){return f[j];}
ll K(int i){return t[i] + s;}

int find(int l,int r,ll k){
	while(l < r){
		int mid = (l + r) >> 1;
		if(Y(q[mid + 1]) - Y(q[mid])> k * (X(q[mid + 1]) - X(q[mid]))) r = mid;
		else l = mid + 1;
		//cout<<mid<<endl;
	}
	return q[r];
}

int main(){
	scanf("%lld%lld",&n,&s);
	for(int i = 1;i <= n; i++){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		t[i] = t[i - 1] + x;
		c[i] = c[i - 1] + y;
	}
	he = 1;ta = 1;
	for(int i = 1;i <= n; i++){
		int j = find(he,ta,t[i] + s);
		f[i] = f[j] + s * c[n] - s * c[j] + t[i] * c[i] - t[i] * c[j];
		while(he < ta && (Y(q[ta]) - Y(q[ta - 1])) * (X(i) - X(q[ta])) >= 
		                 (Y(i) - Y(q[ta]) * (X(q[ta])- X(q[ta - 1]) ) ) ) ta--;
	    q[++ta] = i;
	}
	printf("%lld\n",f[n]);
	return 0;
} 
2021/3/13 15:07
加载中...