提出 #72043954

---

ソースコード 拡げる

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <atcoder/all>
#include <cmath>
#include <string>
#include <bitset>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint;
// using mint = modint1000000007;
// combination
// https://github.com/atcoder/live_library/blob/cb2068b050b3fbeedd39321b3713ed6546fbeffa/comb.cpp#L31
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i = 0; i < (n); ++i)

// int di[] = {1,1,1,0,0,-1,-1,-1};
// int dj[] = {1,0,-1,1,-1,1,0,-1};
// int di[] = {1,1,-1,-1};
// int dj[] = {1,-1,-1,-1};
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};

void chmin(int &x, int y){
  x = min(x,y);
}

void chmax(ll &x, ll y){
  x = max(x,y);
}

// int dist[2][505][505];

int main() {
  int n; cin >> n;
  vector<int> a(n),b(n),c(n);
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> b[i];
  rep(i,n) cin >> c[i];

  vector<ll> sa(n+1),sb(n+1),sc(n+1);
  rep(i,n) sa[i+1] += sa[i]+a[i];
  rep(i,n) sb[i+1] += sb[i]+b[i];
  rep(i,n) sc[i+1] += sc[i]+c[i];

  vector<ll> d(n+1);
  rep(i,n+1) d[i] = sb[i]-sc[i];
  rep(i,n) d[i+1] += d[i];
  set<pair<ll,int>> se;
  for(int i = 2; i <= n-1; i++) se.emplace(d[i],i);
  ll ans = 0;
  for(int x = 1; x <= n-2; x++) {
    ll now = sa[x-1] + sa[0];
    auto[j,y] = *se.rbegin();
    now += sb[y]-sb[x-1];
    now += sc[n]-sc[y];

    // cout << x << " " << y << " " << now << endl;
    // cout << sa[x-1] + sa[0] << endl;
    // cout << sb[y]-sb[x-1] << endl;
    // cout << sc[n]-sc[y] << endl;

    ans = max(ans,now);
    if(x>=3)se.erase(P(d[x],x));
  }
  cout << ans << endl;
  return 0;
}

提出情報

ジャッジ結果