Pop20push21 [TSOH]

The editorial will be posted tomorrow afternoon for sure. Sorry for the inconvenience. :slightly_smiling_face:

3 Likes

My approach was to store the subarray sums where the each element in each subarray is positive,and then pick the maximum 2 sums and sum it and give the answer.
I handled the all negative and 1 positive and others negative cases differently easily,but the still the solution is wrong .
Can u tell the problem in my approach??

Here is my code

#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<pair<int,int>,long> a ,pair<pair<int,int>,long> b){
    return a.second<b.second;
}
int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    
    map<pair<int,int>,long> m;
    long sum=0;
    int beg=-1;
    for(int i=0;i<n;i++){
        if(arr[i]>0 && beg==-1){
        sum+=arr[i];
        beg=i;
        }
        else if(arr[i]>0 && beg>=0)
        sum+=arr[i];
        else if(arr[i]<=0 && sum>0){
            m.insert({{beg,i-1},sum});
            sum=0;
            beg=-1;
        }
    }
    if(sum>0){
        m.insert({{beg,n-1},sum});
        sum=0;
        beg=-1;
    }
    
    /*
    for(auto i=m.begin();i!=m.end();i++){
        cout<<(i->first).first<<" "<<(i->first).second<<"    "<<i->second<<endl;
    }
    */
    
    if(m.size()==0){
        sort(arr,arr+n);
        cout<<arr[n-1]+arr[n-2]<<endl;
    }
    else if(m.size()==1){
        if((m.begin()->first).first==(m.begin()->first).second){
            sort(arr,arr+n);
            cout<<arr[n-1]+arr[n-2]<<endl;
        }
        else
        cout<<(m.begin()->second)<<endl;
    }
    else{
        vector<pair<pair<int,int>,long> > v;
        for(auto &i : m){
            v.push_back(i);
        }
        sort(v.begin(),v.end(),cmp);
        cout<<v[v.size()-1].second+v[v.size()-2].second<<endl;
    }
}

I guess u forgot :frowning:

No @longtimenoshe2 I posted it but they are still not added with all the problems by codechef.

Please check them out below are the links:

POPPUSH1 - POPPUSH1 - Editorial

EASYABC - EASYABC - Editorial

TSOH - TSOH - Editorial

BXRED :BXRED - Editorial

POPPUSH5 - POPPUSH5 – Editorial

1 Like