Submission #1073665

#TimeUsernameProblemLanguageResultExecution timeMemory
1073665duckindogOlympiads (BOI19_olympiads)C++17
44 / 100
2055 ms67228 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 10,
          K = 6 + 10,
          C = 2000 + 10;
int n, k, c;
int a[N][K];

vector<int> allValue;

vector<int> rrh[K];
bool mk[N];
int ma[N];
void recursion(int cnt, int st) { 
  if (cnt > k) { 
    for (int i = 1; i <= k; ++i) ma[i] = 0;
    for (int i = 1; i <= n; ++i) { 
      if (!mk[i]) continue;
      for (int j = 1; j <= k; ++j) ma[j] = max(ma[j], a[i][j]);
    }

    int total = 0;
    for (int i = 1; i <= k; ++i) total += rrh[i][ma[i] - 1];
    allValue.push_back(total);
    return;
  }

  for (int i = st; i <= n; ++i) { 
    if (mk[i]) continue;
    mk[i] = true;
    recursion(cnt + 1, i + 1);
    mk[i] = false;
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k >> c;
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) cin >> a[i][j];
  } 

  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) rrh[j].push_back(a[i][j]);
  }

  for (int i = 1; i <= k; ++i) { 
    sort(rrh[i].begin(), rrh[i].end());
    rrh[i].erase(unique(rrh[i].begin(), rrh[i].end()), rrh[i].end());
  }
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) { 
      int it = upper_bound(rrh[j].begin(), rrh[j].end(), a[i][j]) - rrh[j].begin();
      a[i][j] = it;
    }
  }

  recursion(1, 1);
  sort(allValue.begin(), allValue.end(), greater<>());
  cout << allValue[c - 1] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...