Submission #1275532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275532		sakib_safwan	Feast (NOI19_feast)	C++20	30 / 100	52 ms	8608 KiB

feast

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define endl "\n"
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
// #define int long long

// Don't Start typing till you complete the idea.

// Check these things for WA and before submitting
// 1. Did you clear all the global arrays
// 2. Did you checked your <= >= < >
// 3. Did you take the input properly. Did you use break or return while taking
// input?
// 4. Did you divide by 0.
// 5. Check array , vector , etc size
// 6. in the while loop did you miss something that would cause infinite loop?
// 7. Did you save your dp?
// 8. Are you trying to use something after deleting it?
// 9. Did you read the problem statement wrong?
// 10. Did you check the constrains of the problem properly
// 11. Did you checked for smaller cases like 1 , 0 , etc
// 12. Is it something to with overflow?
// 13. Did you initialized all the variables properly?
// 14. Did you use the formulas correctly?

// STRESS TESTING !!!!!! STRESS TESTING !!!!!
// STRESS Testing Not working?
// Stress test for multiple cases?
// Stress test for big inputs?
// Stress test for really small inputs?
// Even then if it doesn't work -> Did you wrote the wrong Brute force code

// Check these things if you are not generating ideas
// 1. Did you try thinking it in reverse?
// 2. Read the problem statement again
// 3. Check the constraints again
// 4. Try smaller cases in notebook and try to expand
// 5. Think about invariants
// 6. Think simpler ideas maybe?
// 7. Think brute force and try to get something out of it.
// 8. Maybe take a deep breath and take a break for few minutes and drink some
// water? :3

const int N = 3e5 + 9;
ll ara[N];
int n, k;
ll dp[N];
int seg[N];
ll pref[N];
pair<int, int> func(ll cst) {
  for (int i = 1; i <= n + 1; i++) dp[i] = 0, seg[i] = 0;
  dp[n + 1] = pref[n];
  pair<ll, ll> mxv = {dp[n + 1], 0};
  pair<ll, ll> ret = {0, 0};
  for (int i = n; i >= 1; i--) {
    if (mxv.first - pref[i - 1] - cst >= 0) {
      dp[i] = mxv.first - pref[i - 1] - cst;
      seg[i] = mxv.second + 1;
    }
    ret = max(ret, {dp[i], seg[i]});
    mxv = max(mxv, {ret.first + pref[i - 1], ret.second});
    // cout << cst << ' ' << i << ' ' << dp[i] << ' ' << seg[i] << ' ' <<
    // mxv.first
    //  << ' ' << mxv.second << endl;
  }
  return ret;
}

void GG() {
  cin >> n >> k;
  ll tot_seg = 0;
  ll tot_sum = 0;
  bool ok = false;
  for (int i = 1; i <= n; i++) {
    cin >> ara[i];
    if (ara[i] >= 0) {
      if (!ok) tot_seg++, ok = true;
      tot_sum += ara[i];
    } else
      ok = false;
    pref[i] = pref[i - 1] + ara[i];
  }
  // cout << tot_seg << ' ' << tot_sum << endl;
  if (k >= tot_seg) {
    cout << tot_sum << endl;
    return;
  }
  ll l = 0;
  ll r = 1e15;
  ll mid;
  ll cst = 0;
  pair<ll, ll> ans;
  while (l <= r) {
    mid = (l + r) >> 1;
    pair<ll, ll> shei = func(mid);
    // cout << l << ' ' << r << ' ' << mid << ' ' << shei.first << ' '
    //  << shei.second << endl;
    if (shei.second < k)
      r = mid - 1;
    else {
      l = mid + 1;
      ans = shei;
      cst = mid;
    }
  }
  cout << ans.first + cst * k << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int ttc = 1;
  // cin >> ttc;
  // int cnt=0;
  while (ttc--) {
    // cout<<"Case "<<++cnt<<": ";
    GG();
  }
}

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