Submission #1073665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073665		duckindog	Olympiads (BOI19_olympiads)	C++17	44 / 100	2055 ms	67228 KiB

olympiads

#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";
}

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