CSES- Maximum Subarray II | Why is this code giving correct answer?
Difference between en5 and en6, changed 66 character(s)
The first code is giving correct answer while second code is giving wrong answer. The only difference between these two codes is:<br>↵
In the first code the return value is -2*inf in the getmax function while it is -inf in the second code. Can anybody please help me figure out what is the problem?
<br>↵
[Link to Problem](https://cses.fi/problemset/result/902905/)


<spoiler summary="Code 1">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define pii pair<ll,ll>↵
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))↵
#define vi vector<ll>↵
#define vii vector<pii>↵
#define all(x) x.begin(),x.end()↵
#define eb emplace_back↵
#define yes cout<<"YES"<<endl; return;↵
#define no cout<<"NO"<<endl; return;↵
#define flus fflush(stdin); fflush(stdout);↵
#define F first↵
#define S second↵
#define np next_permutation↵
#define inf 1e18↵
#define mod 1000000007↵
#define N 200100↵
#define pi (double)2*acos(0.0)↵
#define minpq priority_queue <ll, vector<ll>, greater<ll>>↵
#define maxpq priority_queue<ll> ↵
void sout(){↵
cout<<endl;↵
}↵
template <typename T,typename... Types>↵
void sout(T var1,Types... var2){↵
cout<<var1<<" ";↵
sout(var2...);↵
}↵
/*******************************************************************/↵
 ↵
 ↵
ll arr[N];↵
ll pre[N];↵
ll tree[4*N];↵
ll n,a,b;↵
void build(ll s,ll e,ll ind=1){↵
if(s==e){↵
tree[ind]=pre[s];↵
return;↵
}↵
ll mid=(s+e)/2;↵
build(s,mid,2*ind);↵
build(mid+1,e,2*ind+1);↵
tree[ind]=max(tree[2*ind],tree[2*ind+1]);↵
}↵
ll getmax(ll s,ll e,ll l,ll r,ll ind=1){↵
if(e<l or s>r)↵
return -2*inf;↵
if(s>=l and e<=r)↵
return tree[ind];↵
ll mid=(s+e)/2;↵
ll a=getmax(s,mid,l,r,2*ind);↵
ll b=getmax(mid+1,e,l,r,2*ind+1);↵
return max(a,b);↵
}↵
ll getmax(ll l,ll r){↵
return getmax(0,n,l,r);↵
}↵
void solve(){↵

cin>>n>>a>>b;↵

rep(i,1,n+1){↵
cin>>arr[i];↵
}↵

pre[0]=0;↵
rep(i,1,n+1){↵
pre[i]=pre[i-1]+arr[i];↵
}↵

build(0,n);↵
ll ans=-inf;↵
for(ll i=a;i<=n;i++){↵
ll x=getmax(min(n,i+1),min(n,i+b-a));↵
x=x-pre[i];↵
x=max(x,0LL);↵
// sout("x",x);↵
ll loc=x+pre[i]-pre[i-a];↵
ans=max(ans,loc);↵
}↵
cout<<ans<<endl;↵
}↵
 ↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
// cin>>t;↵
t=1;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵


</spoiler>↵


<spoiler summary="Code 2">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define pii pair<ll,ll>↵
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))↵
#define vi vector<ll>↵
#define vii vector<pii>↵
#define all(x) x.begin(),x.end()↵
#define eb emplace_back↵
#define yes cout<<"YES"<<endl; return;↵
#define no cout<<"NO"<<endl; return;↵
#define flus fflush(stdin); fflush(stdout);↵
#define F first↵
#define S second↵
#define np next_permutation↵
#define inf 1e18↵
#define mod 1000000007↵
#define N 200100↵
#define pi (double)2*acos(0.0)↵
#define minpq priority_queue <ll, vector<ll>, greater<ll>>↵
#define maxpq priority_queue<ll> ↵
void sout(){↵
cout<<endl;↵
}↵
template <typename T,typename... Types>↵
void sout(T var1,Types... var2){↵
cout<<var1<<" ";↵
sout(var2...);↵
}↵
/*******************************************************************/↵
 ↵
 ↵
ll arr[N];↵
ll pre[N];↵
ll tree[4*N];↵
ll n,a,b;↵
void build(ll s,ll e,ll ind=1){↵
if(s==e){↵
tree[ind]=pre[s];↵
return;↵
}↵
ll mid=(s+e)/2;↵
build(s,mid,2*ind);↵
build(mid+1,e,2*ind+1);↵
tree[ind]=max(tree[2*ind],tree[2*ind+1]);↵
}↵
ll getmax(ll s,ll e,ll l,ll r,ll ind=1){↵
if(e<l or s>r)↵
return -inf;↵
if(s>=l and e<=r)↵
return tree[ind];↵
ll mid=(s+e)/2;↵
ll a=getmax(s,mid,l,r,2*ind);↵
ll b=getmax(mid+1,e,l,r,2*ind+1);↵
return max(a,b);↵
}↵
ll getmax(ll l,ll r){↵
return getmax(0,n,l,r);↵
}↵
void solve(){↵

cin>>n>>a>>b;↵

rep(i,1,n+1){↵
cin>>arr[i];↵
}↵

pre[0]=0;↵
rep(i,1,n+1){↵
pre[i]=pre[i-1]+arr[i];↵
}↵

build(0,n);↵
ll ans=-inf;↵
for(ll i=a;i<=n;i++){↵
ll x=getmax(min(n,i+1),min(n,i+b-a));↵
x=x-pre[i];↵
x=max(x,0LL);↵
// sout("x",x);↵
ll loc=x+pre[i]-pre[i-a];↵
ans=max(ans,loc);↵
}↵
cout<<ans<<endl;↵
}↵
 ↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
// cin>>t;↵
t=1;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵


</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Rock2000 2020-08-26 18:23:21 66
en5 English Rock2000 2020-08-26 18:10:30 10
en4 English Rock2000 2020-08-26 17:59:58 2 Tiny change: 'isThe first ' -> 'The first '
en3 English Rock2000 2020-08-26 17:59:08 3
en2 English Rock2000 2020-08-26 17:58:30 13 Tiny change: 'The first ' -> 'isThe first '
en1 English Rock2000 2020-08-26 17:57:55 4405 Initial revision (published)