QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122867 | #1808. Efficient Partitioning | solemntee | ML | 0ms | 3700kb | C++20 | 2.2kb | 2023-07-11 13:16:16 | 2023-07-11 13:16:18 |
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(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...