Submission #666354

#	Time	Username	Problem	Language	Result	Execution time	Memory
666354		MilosMilutinovic	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	2065 ms	22772 KiB

prison

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, d, t;
  cin >> n >> d >> t;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  const long long inf = 2e16;
  vector<pair<long long, int>> dp(n + 1, {inf, 0});
  auto Check = [&](long long x) {
    dp = vector<pair<long long, int>>(n + 1, {inf, 1e9});
    dp[n] = {0, 0};
    for (int i = n - 1; i >= 0; i--) {
      int mn = 1e9;
      int delta = 0;
      for (int j = i; j < n; j++) {
        mn = min(mn, a[j]);
        if (mn <= t) {
          delta += 1;
        }
        dp[i] = min(dp[i], {dp[j + 1].first + x + delta, dp[j + 1].second + 1});
      }
    }
    return dp[0].second <= d;
  };
  long long l = 0, r = inf, ans = 0;
  while (l <= r) {
    int mid = l + r >> 1;
    if (Check(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  Check(ans);
  cout << dp[0].first - ans * dp[0].second - ans << '\n';
  return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20