作业介绍

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300005;
#define int long long
int n,s;
int t[N],sum[N];
int f[N],q[N],tail=-1,head=0;
/*
f[i] = f[j] + t[i]*(sum[i]-sum[j])+s*(sum[n]-sum[j])
f[i] = f[j] + t[i]*sum[i]-t[i]*sum[j]+s*sum[n]-s*sum[j]
f[j]-s*sum[j] = t[i]*sum[j] + f[i]-s*sum[n]-t[i]*sum[i]

(sum[j],f[j]-s*sum[j])
*/
int X(int i){
	return sum[i];
}
int Y(int i){
	return f[i]-s*sum[i];
}
double slope(int i,int j){
	return double(Y(i)-Y(j))/double(X(i)-X(j));
}
signed main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>sum[i];
		t[i]+=t[i-1];
		sum[i]+=sum[i-1];
	}
	q[++tail] = 0;
	for(int i=1;i<=n;i++){
		while(tail>head && slope(q[head],q[head+1])<t[i])head++;
		int j = q[head];
		f[i] = f[j]+t[i]*(sum[i]-sum[j])+s*(sum[n]-sum[j]);
		while(tail>head && slope(i,q[tail-1])<=slope(q[tail],q[tail-1]))--tail;
		q[++tail] = i;
	}
	cout<<f[n]<<endl;
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+5;
int n,s,t[N],sum[N],f[N],stk[N],top;
/*
f[i] = f[j]+t[i]*(sum[i]-sum[j])+s*(sum[n]-sum[j])
 = f[j]-t[i]*sum[j]-s*sum[j]
t[i]*sum[j] + f[i]-s*sum[n]+t[i]*sum[i] = f[j]-s*sum[j]
*/
int X(int i){
	return sum[i];
}
int Y(int i){
	return f[i]-s*sum[i];
}
/*
double k = Y(i)-Y(j)/X(i)-X(j)
return k<=t[i]
*/
int Search(int i)
{
	int l=0,r=top-1;
	int res = -1;
	while(l<=r){
		int mid = (l+r)>>1;
		if(t[i]*(X(stk[mid+1])-X(stk[mid]))<(Y(stk[mid+1])-Y(stk[mid]))){
			r = mid-1;
			res = mid;
		}
		else l = mid+1;
	}
//	cout<<res<<" "<<top<<endl;
	if(res==-1)return stk[top];
	return stk[res];
}
signed main()
{
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>sum[i];
		t[i]+=t[i-1];
		sum[i]+=sum[i-1];
	}
	for(int i=1;i<=n;i++){
		int j = Search(i);
		f[i] = f[j]+t[i]*(sum[i]-sum[j])+s*(sum[n]-sum[j]);
	//	cout<<i<<" "<<j<<" "<<f[i]<<endl;
		while(top && ((Y(i)-Y(stk[top]))*(X(i)-X(stk[top-1])))<=((Y(i)-Y(stk[top-1]))*(X(i)-X(stk[top]))))top--;
		stk[++top] = i; 
	}
	cout<<f[n]<<endl;
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4+5;
int n,q[N],tail=-1,head=0;
struct node{
	int w,h;
}a[N],b[N];
int f[N];
bool cmp(node a,node b){
	if(a.w==b.w)return a.h>b.h;
	return a.w>b.w;
}
int X(int i){
	return b[i+1].w;
}
int Y(int i){
	return f[i];
}
double slope(int i,int j){
	return double(Y(i)-Y(j))/double(X(i)-X(j));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].h;
	}
	sort(a+1,a+n+1,cmp);
	int m = 0;
	b[++m] = a[1];
	for(int i=2;i<=n;i++){
		if(a[i].h>b[m].h)b[++m] = a[i];
	}
	n = m;
	q[++tail] = 0;
	for(int i=1;i<=n;i++){
		while(tail>head && slope(q[head],q[head+1])>=-b[i].h)head++;
		int j =q[head];
		f[i] = f[j]+b[j+1].w*b[i].h;
		while(tail>head && slope(i,q[tail-1])>=slope(q[tail],q[tail-1]))--tail;
		q[++tail] = i;
	}
	cout<<f[n]<<endl;
	return 0;
}
状态
已结束
题目
11
开始时间
2026-4-16 0:00
截止时间
2026-4-30 23:59
可延期
24 小时