QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122861 | #1808. Efficient Partitioning | solemntee | ML | 0ms | 0kb | C++20 | 2.3kb | 2023-07-11 13:12:17 | 2023-07-11 13:12:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(ll)1e15;
struct segetree{
struct node
{
int ls,rs;
ll sum;
};
vector<node>tree;
segetree(int n=0):tree(20000000){
tree[1]={0,0,-INF};
};
int tot=1;
void create(int p)
{
tree[p].ls=tree[p].rs=0;
tree[p].sum=-INF;
//tree.push_back({0,0,-INF});
}
void update(int p,ll l,ll r,ll x,ll w)
{
//printf("%d %lld %lld %lld %lld\n",p,l,r,x,w);
if(!p)return ;
if(l==r)
{
tree[p].sum=max(w,tree[p].sum);
return ;
}
ll mid=(l+r)/2;
if(x<=mid)
{
if(!tree[p].ls)
{
tree[p].ls=++tot;
create(tot);
}
update(tree[p].ls,l,mid,x,w);
}
if(x>mid)
{
if(!tree[p].rs)
{
tree[p].rs=++tot;
create(tot);
}
update(tree[p].rs,mid+1,r,x,w);
}
tree[p].sum=max(tree[tree[p].ls].sum,tree[tree[p].rs].sum);
}
long long query(int p,ll l,ll r,ll x,ll y)
{
//printf("%d %d %d %d %d\n",p,l,r,x,y);
if(!p)return 0;
if(l>=x&&r<=y)return tree[p].sum;
ll mid=(l+r)/2;
long long sum=-INF;
if(x<=mid&&tree[p].ls)sum=max(sum,query(tree[p].ls,l,mid,x,y));
if(y>mid&&tree[p].rs)sum=max(sum,query(tree[p].rs,mid+1,r,x,y));
return sum;
}
};
int main(){
int n;
scanf("%d",&n);
vector<ll>a(n+1),b(n+1),c(n+1),pre(n+1);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
pre[i]=pre[i-1]+a[i];
}
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
vector<ll>dp(n+1);
segetree T1,T2;
for(int i=1;i<=n;i++){
if(i==1){
dp[i]=a[i]+b[i]+c[i];
}else{
T1.update(1,-INF,INF,dp[i-1]+pre[i-1]-b[i],dp[i-1]);
T2.update(1,-INF,INF,dp[i-1]+pre[i-1]-b[i],b[i]-pre[i-1]);
dp[i]=max(T1.query(1,-INF,INF,-INF,pre[i]+c[i]),T2.query(1,-INF,INF,pre[i]+c[i]+1,INF));
}
}
printf("%lld",dp[n]);
return 0;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
2 1 -1 -1 4 1 -2