daily 2

CF 1209E1

void solve() {
  int n, m;
  cin >> n >> m;
  vector mp(n + 1, vector<int>(m + 1));
  vector dp(m + 1, vector<int>(25));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> mp[i][j];
  for (int i = 1; i <= m; ++i) {
    for (int s = 0; s < (1 << n); ++s) {
      for (int iter = 1; iter <= n; ++iter) {
        int val = 0;
        for (int j = 1; j <= n; ++j) {
          if (s & (1 << j - 1)) {
            val += mp[j][i];
          }
        }
        for (int p = 0; p < (1 << n); ++p) {
          if (!(s & p)) {
            dp[i][s | p] = max(dp[i][s | p], dp[i - 1][p] + val);
          }
        }
        for (int j = 1; j <= n; ++j) {
          mp[j - 1][i] = mp[j][i];
        }
        mp[n][i] = mp[0][i];
      }
    }
  }
  cout << dp[m][(1 << n) - 1] << '\n';
  return;
}

CF 1260D

void solve() {
  int m, n, k, t;
  cin >> m >> n >> k >> t;
  vector<int> a(m + 1);
  vector<node> s(k + 1);
  vector<int> dif(n + 2);
  for (int i = 1; i <= m; ++i) cin >> a[i];
  for (int i = 1; i <= k; ++i) {
    cin >> s[i].l >> s[i].r >> s[i].d;
  }
  sort(a.begin() + 1, a.end(),greater<int>());
  auto check = [&](int cur) {
    int sum = 0;
    fill(dif.begin(), dif.end(), 0);
    for (int i = 1; i <= k; ++i) {
      if (s[i].d > cur) {
        dif[s[i].l]++;
        dif[s[i].r + 1]--;
      }
    }
    for (int i = 1; i <= n + 1; ++i) {
      dif[i] += dif[i - 1];
      if (dif[i]) {
        sum += 3;
      } else {
        sum += 1;
      }
    }
    return sum <= t;
  };
  int l = 0, r = m+1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(a[mid])) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  cout << max(r-1,0) << '\n';
  return;
}