QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122867#1808. Efficient PartitioningsolemnteeML 0ms3700kbC++202.2kb2023-07-11 13:16:162023-07-11 13:16:18

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:16:18]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3700kb
  • [2023-07-11 13:16:16]
  • 提交

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(2,{0,0,-INF}){};
    int tot=1;
    void create(int p)
    {
        if(p>=100000)printf("%d\n",p);
        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: 100
Accepted
time: 0ms
memory: 3684kb

input:

2
1 -1
-1 4
1 -2

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

1
1000000000
1000000000
1000000000

output:

3000000000

result:

ok answer is '3000000000'

Test #3:

score: -100
Memory Limit Exceeded

input:

11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -72...

output:

100000
100001
100002
100003
100004
100005
100006
100007
100008
100009
100010
100011
100012
100013
100014
100015
100016
100017
100018
100019
100020
100021
100022
100023
100024
100025
100026
100027
100028
100029
100030
100031
100032
100033
100034
100035
100036
100037
100038
100039
100040
100041
100042...

result: