Waiting for the dawn

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

CF 1367E

void solve() {
  int n, k;
  cin >> n >> k;
  vector<ll> cnt(26);
  function<bool(int, int)> check =
      [&](int total, int rep) {  // total: the number of current
        for (int i = 0; i < 26; ++i) {
          total -= cnt[i] / rep;
          if (total <= 0) return true;
        }
        return false;
      };
  string s;
  ll ans = 0;
  cin >> s;
  for (int i = 0; i < s.size(); ++i) {
    cnt[s[i] - 'a']++;
    ans = max(ans, cnt[s[i] - 'a']);
  }
  vector<int> fac;
  for (int i = 2; i <= k; ++i) {
    if (k % i == 0) {
      fac.push_back(i);
    }
  }

  for (int &f : fac) {
    int l = 1, r = n / f;  // 循环节的数量
    while (l <= r) {
      int mid = (l + r) >> 1;  //
      if (check(f, mid)) {
        ans = max(ans, 1ll * mid * f);
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  cout << ans << '\n';
  return;
}

CF 1363E

daily codeforces

CF 1335E2

void solve() {
  int n, ans = 0;
  cin >> n;
  vector<int> pos[MAXN];
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= 200; ++j) {
        cnt[i][j] = 0;
    }
  }
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    memcpy(cnt[i], cnt[i - 1], sizeof(cnt[i - 1]));
    cnt[i][a[i]]++;
    pos[a[i]].push_back(i);
  }
  for (int i = 1; i <= 200; ++i) {
    int sz = pos[i].size();
    ans = max(ans, sz);
    for (int j = 0; j < sz / 2; ++j) {
      int l = pos[i][j], r = pos[i][sz - j - 1] - 1;
      for (int k = 1; k <= 200; ++k) {
        int mid = cnt[r][k] - cnt[l][k];
        ans = max(ans, (j + 1) * 2 + mid);
      }
    }
  }
  cout << ans << '\n';
  return;
}

daily codeforces

daily codeforces