QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122861#1808. Efficient PartitioningsolemnteeML 0ms0kbC++202.3kb2023-07-11 13:12:172023-07-11 13:12:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 13:12:20]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-07-11 13:12:17]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

2
1 -1
-1 4
1 -2

output:


result: