제출 #1222666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222666		i_love_spring	Hacker (BOI15_hac)	C++20	0 / 100	0 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) + 1) / 2;
    cerr << "1 " << i + 1 << " " << 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 - 1]);
      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 - 1]);
      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 r = (i - x) / 2,l = (x + (n - i) + 1) / 2;
    //cerr << "1 " << i + 1 << " " << 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 - 1]);
      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 - 1]);
      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++) {
      if (i == j) continue;
      ans = max(ans,dp[j + 1]);
    }
  }
  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