社区讨论

帮忙看看我家孩子的CSP-J T2 50pts

学术版参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo6wq1v2
此快照首次捕获于
2023/10/26 16:13
2 年前
此快照最后确认于
2023/11/02 11:20
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,d,a[10001],v[10001],f[10001],sheng,sum,t;
struct num{
	long long x,id;
};
stack<num>s;
int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%lld%lld",&n,&d);
	for(long long i=1;i<n;i++)scanf("%lld",&v[i]);
	for(long long i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(long long i=1;i<n;i++)v[i]+=v[i-1];
	for(long long i=1;i<=n;i++){
		while(!s.empty()&&a[i]<s.top().x)f[s.top().id]=i,s.pop();
		s.push((num){a[i],i});
	}
	for(long long i=1;i<=n;i++)if(f[i]==0)f[i]=n;
	
	for(long long i=1;i!=n;i=f[i]){
		t=max(0ll,(v[f[i]-1]-v[i-1]-sheng+d-1)/d);
		sum+=t*a[i];
		sheng=d*t-(v[f[i]-1]-v[i-1]-sheng);
	}
	printf("%lld",sum);
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...