QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122864#1808. Efficient PartitioningsolemnteeML 1ms3704kbC++202.2kb2023-07-11 13:15:442023-07-11 13:15:46

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:15:46]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3704kb
  • [2023-07-11 13:15:44]
  • 提交

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>=100)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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3700kb

input:

2
1 -1
-1 4
1 -2

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3704kb

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:

100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
...

result: