Submission #6789081

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll N, K, s=0;
  cin>>N>>K;
  vector<ll> a(N);
  rep(i,0,N){
    cin>>a[i];
    s+=a[i];
  }

  // 約数一覧
  set<ll> divisors;
  for (ll i=1; i*i<=s; i++) {
    if (s%i == 0) {
      divisors.insert(i);
      divisors.insert(s/i);
    }
  }

  ll ans = -1;
  for (auto d: divisors) {
    vector<ll> x(N);
    vector<ll> psum1(N+2, 0); // psum1[i]: i番目までのあまりの総和
    vector<ll> psum2(N+2, 0); // psum2[i]: i番目以降のあまりの総和
    rep(i,0,N){
      x[i] = a[i] % d;
    }
    sort(begin(x),end(x));

    rep(i,1,N+1){
      psum1[i] = psum1[i-1] + x[i-1];
    }
    for (int i=N; i>=1; i--){
      psum2[i] = psum2[i+1] + x[i-1];
    }
    rep(i,0,N+1){
      // [0 i]  を -1
      // [i+1 N+1]を1
      // if (d==7) {
      //   printf("psum1[%d]=%d\n", i,   psum1[i]);
      //   printf("psum2[%d]=%d\n", i+1, psum2[i+1]);
      //   printf("d*(%d) - psum2[%d]=%d\n", N-i, i+1, d*(N-i+1) - psum2[i+1]);
      //   cout<<endl;
      // }
      if (max(psum1[i], d*(N-i) - psum2[i+1]) <= K) {
        ans=max(ans,d);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result