oj.uz

Submission #657444

# Submission time Handle Problem Language Result Execution time Memory
657444 2022-11-09T20:55:02 Z bicsi Olympiads (BOI19_olympiads) C++14
100 / 100
 455 ms 112936 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2284 KB Output is correct
2 Correct 20 ms 5116 KB Output is correct
3 Correct 25 ms 7624 KB Output is correct
4 Correct 3 ms 596 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7736 KB Output is correct
2 Correct 21 ms 4280 KB Output is correct
3 Correct 20 ms 3564 KB Output is correct
4 Correct 28 ms 3524 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5228 KB Output is correct
2 Correct 10 ms 2900 KB Output is correct
3 Correct 298 ms 47520 KB Output is correct
4 Correct 381 ms 92616 KB Output is correct
5 Correct 299 ms 49128 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2284 KB Output is correct
2 Correct 20 ms 5116 KB Output is correct
3 Correct 25 ms 7624 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 30 ms 7736 KB Output is correct
6 Correct 21 ms 4280 KB Output is correct
7 Correct 20 ms 3564 KB Output is correct
8 Correct 28 ms 3524 KB Output is correct
9 Correct 24 ms 5228 KB Output is correct
10 Correct 10 ms 2900 KB Output is correct
11 Correct 298 ms 47520 KB Output is correct
12 Correct 381 ms 92616 KB Output is correct
13 Correct 299 ms 49128 KB Output is correct
14 Correct 10 ms 1492 KB Output is correct
15 Correct 253 ms 39224 KB Output is correct
16 Correct 387 ms 77532 KB Output is correct
17 Correct 455 ms 112936 KB Output is correct
18 Correct 367 ms 71636 KB Output is correct
19 Correct 10 ms 3028 KB Output is correct