Submission #1364631

#TimeUsernameProblemLanguageResultExecution timeMemory
1364631jumpHacker (BOI15_hac)C++20
20 / 100
268 ms31764 KiB
#include <bits/stdc++.h>
#define int long long

int n;
int arr[500500];
int pref[1000500];
int end[1500500];
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for(int i=1;i<=n;i++){
    std::cin >> arr[i];
    pref[i]=pref[i-1]+arr[i];
  }
  for(int i=n+1;i<=n*2;i++){
    pref[i]=pref[i-1]+arr[i-n];
  }
  // for(int i=2*n+1;i<=n*3;i++){
  //   pref[i]=pref[i-1]+arr[i-2*n];
  // }
  for(int i=n+1;i<=n*2;i++){
    end[i]=pref[i]-pref[i-(n/2)];
    //std::cout << end[i] << ' ';
  }
  for(int i=n*2+1;i<=n*3;i++){
    end[i]=end[i-n];
  }
  std::multiset<int> s;
  int ssize=(n)/2;
  int max=0;
  for(int i=n+1;i<=n*3;i++){
    s.insert(end[i]);
    if(s.size()<ssize)continue;
    if(s.size()>ssize)s.erase(s.find(end[i-ssize]));
    auto itr = s.end();
    --itr;
    max=std::max(pref[n]-*itr,max);
  }
  std::cout << max;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...