Submission #73263526

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using mint = modint998244353;
#define rep(i, b) for (int i = 0; i < (int)(b); i++)
#define oke  cout << "Yes" << endl;
#define dame  cout << "No" << endl;
#define muri cout << -1 << endl;
#define repp(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define uni(vec2) vec2.erase(unique(vec2.begin(), vec2.end()), vec2.end())

ll inf = 1001001001001001;
ull m998 = 998244353;
//時計回り




//累積和
vector<ull> prefix_sum(vector<ull> v) {
  int n = v.size();
  vector<ull> res(n);
  rep(i, n) {
    res[i] = v[i];
    if (i != 0) res[i] += res[i-1];
  }
  return res;
}

//素因数分解
vector<pair<ull, ull>> prime_factorize(ull x) {
  ull y = sqrt(x);
  vector<pair<ull, ull>> res;
  for (ull i=2; i<=y; i++) {
    if (x%i == 0) {
      ull cnt = 0;
      while (x%i == 0) {
        cnt++;
        x/=i;
      }
      res.pb({i, cnt});
    }
  }
  if (x > 1) res.pb({x, 1});
  return res;
}

ull pow(ull x,ull n) {
  ull res = 1;
  while (n > 0) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}

//素数列挙
vector<ull> prime(ull n) {
  vector<bool> check(n+1, true);
  check[0] = false;
  check[1] = false;
  for (ull i = 2; i*i <= n; i++) {
    if (!check[i]) continue;
    if (n%i == 0) {
      for (ull j=2*i; j<=n; j+=i) check[j] = false;
    }
  }
  vector<ull> res;
  for (ull i = 2; i <= n; i++) if (check[i]) res.pb(i);
  return res;
}

/*setで区間管理するやつ
ll l, r;
    cin >> l >> r;
    l--; r--;
    ll nl = l, nr = r;
    auto it = st.upper_bound(l);
    it--;
    ll fl = *it, fr = mp[fl];
    set<ll> kesu;
    if (l <= fr) {
      nl = fl;
      nr = max(nr, mp[fl]);
      kesu.insert(fl);
    }
    it++;
    while (*it <= r) {
      kesu.insert(*it);
      nr = max(mp[*it], r);
      it++;
    }
    for (auto c: kesu) {
      kuro -= abs(mp[c] - c)+1;
      st.erase(c);
    }
    st.insert(nl);
    kuro += abs(nr-nl)+1;
    mp[nl] = nr;
 */

template <typename T>
struct SegmentTree {
  function<T(T, T)> op;
  T e;
  int n = 1;
  vector<T> data;
  SegmentTree(int N, function<T(T, T)> op, T e) : op(op), e(e) {
    while (n < N) n *= 2;
    data = vector<T>(2*n, e);
  }
  void set(int i, T val) {
    i += n;
    data[i] = val;
    while (i > 1) {
      i /= 2;
      data[i] = op(data[i*2], data[i*2+1]);
    }
  }

  //足す
  void set2(int i, T val) {
    i += n;
    data[i] += val;
    while (i > 1) {
      i /= 2;
      data[i] = op(data[i*2], data[i*2+1]);
    }
  }

  //半開区間でもらう
  T query(int l, int r) {
    l += n;
    r += n;
    T l_val = e, r_val = e;
    while (l < r) {
      if (l%2 == 1) {
        l_val = op(l_val, data[l]);
        l++;
      }
      if (r%2 == 1) {
        r--;
        r_val  = op(r_val, data[r]);
      }
      l /= 2;
      r /= 2;
    }
    return op(l_val, r_val);
  }
};

int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  //にぶたん、負担量の最小値をx以上にできるか
  ll ok = 0, ng = 1e17;
  while (ok+1 < ng) {
    ll m = (ok+ng)/2;
    vector<ll> load(k, 0);
    int now = 0;
    rep(i, k) {
      //cout << load[i] << " " << m << endl;
      while (now < n && load[i] < m) {
        load[i] += a[now];
        now++;
      }
    }
    ll cur = 1e17;
    rep(i, k) cur = min(cur, load[i]);
    if (cur >= m) ok = m;
    else ng = m;
  }
  cout << ok << endl;
}

Submission Info

Judge Result