Submission #1314674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314674		joshjuice	Feast (NOI19_feast)	C++20	100 / 100	105 ms	5076 KiB

feast

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;

#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define ppf pop_front
#define pf push_front
#define bk back()
#define frnt front()
#define ins insert
#define er erase
#define sc second
#define fr first
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define REP(i,n) for (int i = 0; i < n; ++i)
#define REP1(i,n) for (int i = 1; i <= n; ++i)
#define REPV(i,n) for (int i = n-1; i >= 0; --i)
#define REPV1(i, n) for (int i = n; i > 0; --i)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define MNTO(x,y) x = min(x, (__typeof__(x))y)
#define MXTO(x,y) x = max(x, (__typeof__(x))y)

pli solve(const vll &a, ll l) {
  int n = a.size();
  vll s(n+1, 0);
  REP(i, n) s[i+1] = s[i]+a[i];
  ll pv = 0, bpv = 0;
  int pc = 0, bpc = 0;
  REP1(i, n) {
    ll vs = pv;
    int cs = pc;
    ll vt = bpv+s[i]-l;
    int ct = bpc+1;
    ll cv;
    int cc;
    if (vt > vs || (vt == vs && ct > cs)) {
      cv = vt;
      cc = ct;
    } else {
      cv = vs;
      cc = cs;
    }
    ll cp = cv -s[i];
    if (cp > bpv || (cp == bpv && cc > bpc)) {
      bpv = cp;
      bpc = cc;
    }
    pv = cv;
    pc = cc;
  }
  return {pv, pc};
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, k;
  cin >> n >> k;
  vll a(n);
  REP(i, n) cin >> a[i];
  auto base = solve(a, 0);
  if (base.sc <= k) {
    cout << base.fr;
    return 0;
  }
  ll lo = 1, hi = 1e14;
  while (lo <= hi) {
    ll mid = (lo+hi) >> 1;
    auto res = solve(a, mid);
    if (res.sc > k) {
      lo = mid+1;
    } else {
      hi = mid-1;
    }
  }
  auto finaldp = solve(a, lo);
  ll dpval = finaldp.fr;
  int t = finaldp.sc;
  ll ans = dpval + lo*t;
  cout << ans;
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29