daily 2

CF 940E

void solve() {
  int n, c;
  cin >> n >> c;
  vector<int> a(n + 1);
  ll sum = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
  } 
  deque<int> q;
  vector<ll> dp(n + 1);
  for (int i = 1; i <= n; ++i) {
    // we maintain a queue to store the increasing queue
    while(q.size() && a[q.back()] >= a[i]) q.pop_back();
    q.push_back(i);
    while(q.size() && i - q.front() >= c) q.pop_front();
    if(i >= c) dp[i] = max(dp[i - 1], dp[i - c] + a[q.front()]);
  }
  cout << sum - dp[n] << '\n';
  return ;
}

CF 580D

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  vector<vector<ll>> dp(n,
                        vector<ll>(1 << n));  // the status is sta and ends in i
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    dp[i][1 << i] = a[i];
  }
  int u, v, c;
  vector<vector<int>> mp(n, vector<int>(n));
  for (int i = 0; i < k; ++i) {
    cin >> u >> v >> c;
    --u, --v;
    mp[u][v] = c;
  }
  for (int sta = 0; sta < (1 << n); ++sta) {
    for (int i = 0; i < n; ++i) {
      if (!(sta & (1 << i))) continue;
      for (int j = 0; j < n; ++j) {
        if (i == j || !(sta & (1 << j))) continue;
        dp[i][sta] = max(dp[i][sta], dp[j][sta ^ (1 << i)] + mp[j][i] + a[i]);
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i < (1 << n); ++i) {
    if (__builtin_popcount(i) != m) {
      continue;
    }
    for (int j = 0; j < n; ++j) {
      ans = max(ans, dp[j][i]);
    }
  }
  cout << ans << '\n';
  return;
}