Waiting for the dawn

daily codeforces

daily codeforces

daily codeforces

daily codeforces

daily codeforces

CF 1384B1

void solve() {
  int n, k ,l;
  cin >> n >> k >> l; 
  int N = n * k + n;
  int mod = 2 * k;
  vector<int> p(2 * k + 3);
  vector<int> d(n + 1);
  iota(p.begin(), p.begin() + k + 1, 0);
  for (int i = 1; i <= n; ++i) cin >> d[i];
  // p = [0, 1, 2, ... k - 1, k, k - 1, .... 1]
  for (int i = k + 1; i <= 2 * k; ++i) {
    p[i] = 2 * k - i;
  }
  vector dp(N + 1, vector<int>(n + 1));
  for (int i = 0; i <= N; ++i) {
    dp[i][0] = 1;
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= n; ++j) {
      dp[i][j] = 0;
      if (d[j] + p[i % mod] <= l) {
        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - 1];
      }
    }
    if (dp[i][n]) {
      cout << "Yes" << '\n';
      return;
    }
  }
  cout << "No" << '\n';
  return ;
}

CF 1383B

CF 1379C

struct node {
  ll a, b;
};
void solve() {
  int n, m;
  cin >> n >> m;
  vector<node> a(m + 1);
  ll cur_max = 0;
  for (int i = 1; i <= m; ++i) {
    cin >> a[i].a >> a[i].b;
    cur_max = max(a[i].a, cur_max);
  }
  sort(a.begin() + 1, a.begin() + m + 1, [&](node a, node b) {
    if (a.a == b.a) return a.b > b.b;
    return a.a > b.a;
  });
  vector<ll> sum(m + 1), current(N);

  for (int i = 1; i <= m; ++i) {
    sum[i] = sum[i - 1] + a[i].a;
    current[i] = a[i].a;
  }
  ll ans = 0;
  for (int i = 1; i <= m; ++i) {
    int pos = lower_bound(current.begin() + 1, current.begin() + 1 + m, a[i].b, greater<int>()) - current.begin();
    --pos;
    if (pos > n) {
      ans = max(ans, sum[n]);
    } else if (pos < i) {
      ans = max(ans, sum[pos] + a[i].a + (n - pos - 1) * a[i].b);
    } else {
      ans = max(ans, (n - pos) * a[i].b + sum[pos]);
    }
  }
  cout << ans << '\n';
  return;
}

CF 1381B

CF 1370D