oj.uz

Submission #854524

# Submission time Handle Problem Language Result Execution time Memory
854524 2023-09-27T20:22:36 Z tvladm2009 Olympiads (BOI19_olympiads) C++17
44 / 100
 576 ms 18616 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 500 + 7;
const int K = 10;
const int MX = 100 + 7;
int score[N][K];
int f[K][MX];
int n, k, c;
vector<int> team, v;

void rec(int cnt = 1) {
  if (cnt == k + 1) {
    vector<int> total(k + 1, 0);
    for (auto &i : team) {
      for (int j = 1; j <= k; j++) {
        total[j] = max(total[j], score[i][j]);
      }
    }
    int now = 0;
    for (int j = 1; j <= k; j++) {
      now += total[j];
    }
    v.push_back(now);
    return;
  }
  int start = (team.empty() ? 1 : team.back() + 1);
  for (int i = start; i <= n; i++) {
    team.push_back(i);
    rec(cnt + 1);
    team.pop_back();
  }
}

signed main() {
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  cin >> n >> k >> c;
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      cin >> score[i][j];
      mx = max(mx, score[i][j]);
    }
  }

  if (mx <= 10) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= k; j++) {
        f[j][score[i][j]]++;
      }
    }
    vector<int> config_final;
    function<void(int)> solve = [&](int lvl) {
      if (lvl == k + 1) {
        ll ways = 1;
        for (int i = 1; i <= k; i++) {
          ways *= f[i][config_final[i - 1]];
        }
        c -= ways;
        if (c <= 0) {
          int sol = 0;
          for (auto &i : config_final) {
            sol += i;
          }
          cout << sol << "\n";
          exit(0);
        }
        return;
      }
      for (int i = mx; i >= 1; i--) {
        config_final.push_back(i);
        solve(lvl + 1);
        config_final.pop_back();
      }
    };
    solve(1);
    return 0;
  }


  rec();
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  cout << v[c - 1] << "\n";
  return 0;
}
/**

dp[i][mxa][mxb] = ?

**/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 992 KB Output is correct
2 Correct 9 ms 992 KB Output is correct
3 Correct 8 ms 1004 KB Output is correct
4 Correct 5 ms 992 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 18344 KB Output is correct
2 Correct 528 ms 18616 KB Output is correct
3 Correct 576 ms 17848 KB Output is correct
4 Correct 531 ms 18472 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 10 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 992 KB Output is correct
2 Correct 9 ms 992 KB Output is correct
3 Correct 8 ms 1004 KB Output is correct
4 Correct 5 ms 992 KB Output is correct
5 Correct 524 ms 18344 KB Output is correct
6 Correct 528 ms 18616 KB Output is correct
7 Correct 576 ms 17848 KB Output is correct
8 Correct 531 ms 18472 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 10 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -