Submission #1222679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222679		i_love_spring	Hacker (BOI15_hac)	C++20	0 / 100	177 ms	2628 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 500005;
int a[N],n;
ll ans = 0,dp[N],pref[N],suff[N];
void comp(int x) {
  memset(dp,0,n + 5);
  memset(pref,0,n + 5);
  memset(suff,0,n + 5);
  for (int i = 1; i <= n;i++) pref[i] = pref[i - 1] + a[i];
  for (int i = n; i > 0;i--) suff[i] = suff[i + 1] + a[i];
  for (int i = x + 1; i <= n;i++) {
    int r = (i - x) / 2,l = (x + (n - i)) / 2;
   // cerr << x << " " << i  << " " << l << " " << r << "\n";
    dp[i] = a[x];
    if (l % 2 && r % 2) {
      if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
      else dp[i] += (pref[x - 1] - pref[x - l - 1]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
      else dp[i] += pref[x + r] - pref[x];
      int p1 = (x - l + n) % n, p2 = (x + r) % n;
      if (p1 == 0) p1 = n;
      if (p2 == 0) p2 = n;
      dp[i] -= min(a[p1],a[p2]);
    }else {
      int p = 0, p1 = n;
      if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
      else dp[i] += (pref[x - 1] - pref[x - l - 1]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
      else dp[i] += pref[x + r] - pref[x];
    }
  }
  for (int i = x - 1; i >= 1;i--) {
    int l = (x - i) / 2,r = ((n - x) + i) / 2;
    //cerr << x << " " << i << " " << l << " " << r << "\n";
    dp[i] = a[x];
    if (l % 2 && r % 2) {
      if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
      else dp[i] += (pref[x - 1] - pref[x - l - 1]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
      else dp[i] += pref[x + r] - pref[x];
      int p1 = (x - l + n) % n, p2 = (x + r) % n;
      if (p1 == 0) p1 = n;
      if (p2 == 0) p2 = n;
      dp[i] -= min(a[p1],a[p2]);
    }else {
      int p = 0, p1 = n;
      if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
      else dp[i] += (pref[x - 1] - pref[x - l - 1]);
      if (r > n - x) dp[i] += pref[n] - pref[x] +  pref[(r - (n - x))];
      else dp[i] += pref[x + r] - pref[x];
    }
  }
  
} 
void task1() {
  for (int i = 1; i <= n;i++) {
    comp(i);
    ll cur = 1e18;
    // for (int j = 1; j <= n;j++) cerr << dp[j] << " ";
    // cerr << " ---- \n";
    for (int j = 1; j <= n;j++) if (i!=j) cur = min(cur,dp[j]);
    ans = max(ans,cur);
  }
  cout << ans;
}
void task2() {
  comp(1);
 // for (int i = 1; i <= n;i++) cerr << dp[i] << " ";
//  cerr << "\n";
  for (int i = 1; i <= n;i++) ans = min(ans,dp[i]);
  cout << ans;
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n;i++) cin >> a[i];
  //task2();
  if (n <= 5000) {
    task1();
  }else {
    task2();
  }  

}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

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