Submission #1171440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171440		escobrand	Hacker (BOI15_hac)	C++20	100 / 100	143 ms	28604 KiB

hac

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb emplace_back
#define ll long long 
#define fi first
#define se second
int n,i,m,k;
const int maxn = 1e6 + 10;
ll a[maxn],mx,t[maxn * 4];
int id[maxn];

ll get(int l,int r)
{
  return a[r] - a[l-1];
}

void build(int i,int l,int r)
{
  if(t[i] == 0)t[i] = LLONG_MAX;
  if(l == r)id[l] = i;
  else 
  {
    int mid = (l + r)/2,ii = i + i;
    build(ii,l,mid);
    build(ii+1,mid+1,r);
  }
}

void up(int i,int l,int r,int tl,int tr,ll tmp)
{
  if(tl > r || tr < l || tl > tr)return;
  if(tl >= l && tr <= r)
  {
    t[i] = min(t[i],tmp);
    return;
  }
  int mid = (tl + tr)/2,ii = i + i;
  up(ii,l,r,tl,mid,tmp);
  up(ii+1,l,r,mid+1,tr,tmp);
}

ll get(int i)
{
  i = id[i];
  ll ans = LLONG_MAX;
  while(i)
  {
    ans = min(ans,t[i]);
    i>>=1;
  }
  return ans;
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // freopen("CHONSO.INP","r",stdin);
    // freopen("CHONSO.OUT","w",stdout);
    
    cin>>n;
    
    for(i = 1;i<=n;i++)
    {
      cin>>a[i];
      a[i+n] = a[i];
    }
    for(i = 1;i<=n + n;i++)
    {
      a[i] += a[i-1];
    }
    m = (n + 1)/2;
    build(1,1,n+n);
    
    for(i = 1;i<=n;i++)
    {
      up(1,i,i + m - 1,1,n + n,a[i+m-1] - a[i-1]);
    }
    
    ll mx = LLONG_MIN;
    for(i = 1;i<=n;i++)
    {
      mx = max(mx,min(get(i),get(i+n)));
    }
    cout<<mx;
    
    return 0;
}

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