Submission #1022938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022938		m5588ohammed	Hacker (BOI15_hac)	C++14	100 / 100	173 ms	164692 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int pre[500005],suf[500005],arr[500005]; 
int MX[22][500005],MX2[22][500005];
int n,mx,ans,j;
void sparsMX(){
    for(int k=1;k<=20;k++){
        for(int i=0;i+(1ll<<k-1)<=n;i++) MX[k][i]=max(MX[k-1][i],MX[k-1][i+(1ll<<k-1)]);  
        for(int i=0;i+(1ll<<k-1)<=n+1;i++) MX2[k][i]=max(MX2[k-1][i],MX2[k-1][i+(1ll<<k-1)]);
    }        
}
int findMX(int l,int r){
    int siz=log2(((r-l)+1));
    return max(MX[siz][l],MX[siz][r+1-(1ll<<siz)]);
}
int findMX2(int l,int r){
    int siz=log2(((r-l)+1));
    return max(MX2[siz][l],MX2[siz][r+1-(1ll<<siz)]);
}
int calc1(int i){
    if(n-j<=i) return (i-(n-j)); 
    else return 0;
}
int calc2(int i){
    if(i<=j) return (n+1)-((j-i)+1);
    else return n+1;
}
signed main()
{
    cin>>n;
    j=n/2;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        pre[i]=pre[i-1]+arr[i];
    }
    for(int i=n;i>=1;i--) suf[i]=suf[i+1]+arr[i];
    for(int i=0;i<=n;i++){
        if(i>=j) MX[0][i]=pre[i]-pre[i-j];
        else{
            MX[0][i]=pre[i]+suf[n+1-(j-i)];
        }
    }
    for(int i=n+1;i>=1;i--){
        if((n-i)+1>=j) MX2[0][i]=suf[i]-suf[i+j];
        else{
            MX2[0][i]=suf[i]+pre[j-((n-i)+1)];
        }
    }
    sparsMX();
    for(int i=1;i<=n;i++){
        ans=max(ans,pre[n]-max(findMX(calc1(i),i-1),findMX2(i+1,calc2(i))));    
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'void sparsMX()':
hac.cpp:10:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   10 |         for(int i=0;i+(1ll<<k-1)<=n;i++) MX[k][i]=max(MX[k-1][i],MX[k-1][i+(1ll<<k-1)]);
      |                             ~^~
hac.cpp:10:83: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   10 |         for(int i=0;i+(1ll<<k-1)<=n;i++) MX[k][i]=max(MX[k-1][i],MX[k-1][i+(1ll<<k-1)]);
      |                                                                                  ~^~
hac.cpp:11:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   11 |         for(int i=0;i+(1ll<<k-1)<=n+1;i++) MX2[k][i]=max(MX2[k-1][i],MX2[k-1][i+(1ll<<k-1)]);
      |                             ~^~
hac.cpp:11:88: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   11 |         for(int i=0;i+(1ll<<k-1)<=n+1;i++) MX2[k][i]=max(MX2[k-1][i],MX2[k-1][i+(1ll<<k-1)]);
      |                                                                                       ~^~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40