Submission #40605

#	Time	Username	Problem	Language	Result	Execution time	Memory
40605		Hassoony	Hacker (BOI15_hac)	C++14	100 / 100	320 ms	35580 KiB

hac

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef unsigned long long ll;
typedef double D;
const ll inf=(1ll<<61);
const ll mod=1e9+7;
const int MX=5e5+9;
int n,a[MX],sums[MX],k;
ll b[MX];
ll seg[MX*6];
void build(int node,int l,int r){
    if(l==r){
        seg[node]=b[l];
        return;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    seg[node]=min(seg[node*2],seg[node*2+1]);
}
ll q(int node,int l,int r,int s,int e){
    if(l>e||r<s)return inf;
    if(l>=s&&r<=e)return seg[node];
    int mid=(l+r)/2;
    return min(q(node*2,l,mid,s,e),q(node*2+1,mid+1,r,s,e));
}
int main(){
    cin>>n;
    k=(n/2)+(n%2);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        sums[i]=a[i];
        if(i)sums[i]+=sums[i-1];
    }
    for(int i=0;i<n;i++){
        if(i+k-1<n){
            b[i]=sums[i+k-1];
            if(i)b[i]-=sums[i-1];
            continue;
        }
        b[i]=sums[n-1]-sums[i-1];
        int x=k-(n-i);
        b[i]+=sums[x-1];
    }
    build(1,0,n-1);
    ll ans=0;
    for(int i=0;i<n;i++){
        ll mn=inf;
        if(i-k+1>=0){
            mn=q(1,0,n-1,i-k+1,i);
        }
        else {
            mn=q(1,0,n-1,0,i);
            int x=i+1;
            x=k-x;
            mn=min(mn,q(1,0,n-1,n-x,n-1));
        }
        ans=max(ans,mn);
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:32:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^

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