oj.uz

Submission #657434

# Submission time Handle Problem Language Result Execution time Memory
657434 2022-11-09T20:27:42 Z bicsi Olympiads (BOI19_olympiads) C++14
100 / 100
 1105 ms 112760 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];

  auto push = [&](vector<int>& dp, vector<int>& v, vector<int>& ret, vector<int>& trace) {
    fill(trace.begin(), trace.end(), -1);
    for (int sub = 0; sub < (1 << k); ++sub) {
      int extra = 0;
      for (int i = 0; i < k; ++i)
        if (sub & (1 << i))
          extra += v[i];
      for (int msk = sub; msk < (1 << k); msk = ((msk + 1) | sub)) {
        if (dp[msk ^ sub] < 0) continue;
        int now = dp[msk ^ sub] + extra;
        if (ret[msk] < now) {
          ret[msk] = now;
          trace[msk] = sub;
        }
      }
    }
  };
  
  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 19 ms 5092 KB Output is correct
3 Correct 26 ms 7652 KB Output is correct
4 Correct 3 ms 468 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 7676 KB Output is correct
2 Correct 49 ms 4256 KB Output is correct
3 Correct 51 ms 3496 KB Output is correct
4 Correct 68 ms 3644 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5236 KB Output is correct
2 Correct 22 ms 3020 KB Output is correct
3 Correct 823 ms 47476 KB Output is correct
4 Correct 827 ms 92788 KB Output is correct
5 Correct 819 ms 49120 KB Output is correct
6 Correct 26 ms 1364 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 19 ms 5092 KB Output is correct
3 Correct 26 ms 7652 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 72 ms 7676 KB Output is correct
6 Correct 49 ms 4256 KB Output is correct
7 Correct 51 ms 3496 KB Output is correct
8 Correct 68 ms 3644 KB Output is correct
9 Correct 63 ms 5236 KB Output is correct
10 Correct 22 ms 3020 KB Output is correct
11 Correct 823 ms 47476 KB Output is correct
12 Correct 827 ms 92788 KB Output is correct
13 Correct 819 ms 49120 KB Output is correct
14 Correct 26 ms 1364 KB Output is correct
15 Correct 735 ms 39288 KB Output is correct
16 Correct 1004 ms 77640 KB Output is correct
17 Correct 1105 ms 112760 KB Output is correct
18 Correct 922 ms 71588 KB Output is correct
19 Correct 23 ms 2960 KB Output is correct