Submission #657444

#	Time	Username	Problem	Language	Result	Execution time	Memory
657444		bicsi	Olympiads (BOI19_olympiads)	C++14	100 / 100	455 ms	112936 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, k, c; cin >> n >> k >> c;
  vector<vector<int>> M(n, vector<int>(k));
  for (int i = 0; i < n; ++i) 
    for (int j = 0; j < k; ++j) 
      cin >> M[i][j];

  vector<int> acc(1 << k), tr(1 << k);
  auto push = [&](vector<int>& dp, vector<int>& v, vector<int>& ret, vector<int>& trace) {
    acc = dp; fill(tr.begin(), tr.end(), 0);
    for (int i = 0; i < k; ++i) {
      for (int msk = 0; msk < (1 << k); ++msk) {
        if (msk & (1 << i)) continue;
        if (acc[msk] < 0) continue;
        if (acc[msk | (1 << i)] < acc[msk] + v[i]) {
          acc[msk | (1 << i)] = acc[msk] + v[i];
          tr[msk | (1 << i)] = (tr[msk] | (1 << i));
        }
      }
    }
    for (int i = 0; i < (1 << k); ++i)
      if (ret[i] < acc[i]) 
        ret[i] = acc[i], trace[i] = tr[i];
  };
  
  vector<vector<vector<int>>> suff(n + 1, 
    vector<vector<int>>(k + 1, vector<int>(1 << k, -1)));
  auto trace = suff;
  suff[n][0][0] = 0;
  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j <= k; ++j) suff[i][j] = suff[i + 1][j];
    for (int j = 0; j < k; ++j) 
      push(suff[i + 1][j], M[i], suff[i][j + 1], trace[i][j + 1]);
  }

  priority_queue<tuple<int, int, int, vector<int>>> pq;
  auto push_state = [&](int i, int j, vector<int>& pref) {
    int score = -1;
    for (int msk = 0; msk < (1 << k); ++msk) {
      int oth = (((1 << k) - 1) ^ msk);
      if (pref[msk] < 0 || suff[i][k - j][oth] < 0) continue;
      score = max(score, pref[msk] + suff[i][k - j][oth]);
    }
    pq.emplace(score, i, j, pref);
  };

  vector<int> init(1 << k, -1); init[0] = 0;
  push_state(0, 0, init);

  vector<int> buff(1 << k), npref(1 << k);
  for (int it = 0; it < c; ++it) {
    auto [score, pi, pj, pref] = pq.top(); pq.pop();
    if (it == c - 1) {
      cout << score << endl;
      return 0;
    }
    
    int msk = 0;
    for (msk = 0; msk < (1 << k); ++msk) {
      int oth = (((1 << k) - 1) ^ msk);
      if (pref[oth] < 0 || suff[pi][k - pj][msk] < 0) continue;
      if (score == pref[oth] + suff[pi][k - pj][msk]) break;
    }
    
    int j = pj;
    for (int i = pi; i < n; ++i) {
      fill(npref.begin(), npref.end(), -1);
      push(pref, M[i], npref, buff);
      if (trace[i][k - j][msk] == -1) { // doesn't take
        if (j < k)
          push_state(i + 1, j + 1, npref);
      } else { // takes
        push_state(i + 1, j, pref);
        msk ^= trace[i][k - j][msk];
        ++j; 
        swap(pref, npref);
      }
    }
  }
  return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:56:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     auto [score, pi, pj, pref] = pq.top(); pq.pop();
      |          ^

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32