QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122881 | #1808. Efficient Partitioning | solemntee | WA | 1ms | 3732kb | C++20 | 2.7kb | 2023-07-11 13:28:41 | 2023-07-11 13:28:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(ll)1e18;
ll midd(ll l,ll r){
ll MID=(l+r)/2;
if(MID==r)MID--;
return MID;
}
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=midd(l,r);
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 -INF;
if(l>=x&&r<=y)return tree[p].sum;
ll mid=midd(l,r);
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(){
//printf("%lld\n",midd(-INF-1,-INF));
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;
}
/*
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 -157617655 -801518744 -328729631 -160335217
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3732kb
input:
2 1 -1 -1 4 1 -2
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
1 1000000000 1000000000 1000000000
output:
3000000000
result:
ok answer is '3000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3660kb
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:
1688078973
result:
wrong answer expected '91174984', found '1688078973'