Submission #1222669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222669		i_love_spring	Hacker (BOI15_hac)	C++20	0 / 100	1 ms	328 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 - 1)];
      else dp[i] += (pref[x - 1] - pref[x - l]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x - 1))];
      else dp[i] += pref[x + r] - pref[x];
      dp[i] -= min(a[(x - l + n) % n],a[(x + r) % n]);
    }else {
      int p = 0, p1 = n;
      if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x - 1)];
      else dp[i] += (pref[x - 1] - pref[x - l]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x - 1))];
      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 - 1)];
      else dp[i] += (pref[x - 1] - pref[x - l]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x - 1))];
      else dp[i] += pref[x + r] - pref[x];
      dp[i] -= min(a[(x - l + n) % n],a[(x + r) % n]);
    }else {
      int p = 0, p1 = n;
      if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x - 1)];
      else dp[i] += (pref[x - 1] - pref[x - l]);
      if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x - 1))];
      else dp[i] += pref[x + r] - pref[x];
    }
  }
  
} 
void task1() {
  for (int i = 1; i <= n;i++) {
    comp(i);
    for (int j = 1; j <= n;j++) cerr << dp[j] << " ";
    cerr << "\n";
    for (int j = 1; j <= n;j++) {
      if (i == j) continue;
      ans = max(ans,dp[j]);
    }
  }
  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 = max(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