QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122864 | #1808. Efficient Partitioning | solemntee | ML | 1ms | 3704kb | C++20 | 2.2kb | 2023-07-11 13:15:44 | 2023-07-11 13:15:46 |
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>=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 ...