Submission #217894

#	Time	Username	Problem	Language	Result	Execution time	Memory
217894		quocnguyen1012	Feast (NOI19_feast)	C++14	100 / 100	289 ms	14072 KiB

feast

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 3e5 + 5;

int a[maxn], N, K;
pair<ll, int> f[maxn][2];

pair<ll, int> best(pair<ll, int> a, pair<ll, int> b)
{
  if(a.fi == b.fi) return a.se < b.se ? a : b;
  return a.fi > b.fi ? a : b;
}

pair<ll, int> operator - (pair<ll, int> a, ll x)
{
  return mp(a.fi - x, a.se + 1);
}

pair<ll, int> operator + (pair<ll, int> a, ll x)
{
  return mp(a.fi + x, a.se);
}

pair<ll, int> solve(ll cost)
{
  for(int i = 1; i <= N; ++i){
    f[i][0] = best(f[i - 1][0], f[i - 1][1] - cost);
    f[i][1] = best(f[i - 1][0], f[i - 1][1]) + a[i];
  }
  return best(f[N][0], f[N][1] - cost);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> K;
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
  }
  ll l = 0, r = 1e15, mid;
  while(l <= r){
    mid = (l + r) / 2;
    if(solve(mid).se > K) l = mid + 1;
    else r = mid  - 1;
  }
  cout << solve(l).fi + l * K;
}

• 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