Submission #688515

#TimeUsernameProblemLanguageResultExecution timeMemory
688515stanislavpolynOlympiads (BOI19_olympiads)C++17
44 / 100
592 ms17060 KiB
#include <bits/stdc++.h> #define fr(i, a, b) for (int i = (a); i <= (b); ++i) #define rf(i, a, b) for (int i = (a); i >= (b); --i) #define fe(x, y) for (auto& x : y) #define fi first #define se second #define pb push_back #define mp make_pair #define mt make_tuple #define all(x) (x).begin(), (x).end() #define pw(x) (1LL << (x)) #define sz(x) (int)(x).size() using namespace std; mt19937_64 rng(228); #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define fbo find_by_order #define ook order_of_key template <typename T> bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; } template <typename T> bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; } using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; template <typename T> using ve = vector<T>; int n, k, c; int a[505][7]; ve<int> st; int mx[7]; ve<int> scores; int sum[505]; ve<int> order; void rec(int p = 1) { if (sz(st) == k) { fr (i, 1, k) mx[i] = -1e9; fe (cur, st) { fr (i, 1, k) { umx(mx[i], a[cur][i]); } } int sum = 0; fr (i, 1, k) sum += mx[i]; scores.pb(sum); return; } if (p > n) return; rec(p + 1); st.pb(p); rec(p + 1); st.pop_back(); } int need[7]; int mask[505]; int dp[7][64]; int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else ios::sync_with_stdio(0); cin.tie(0); #endif ve<array<int, 6>> res; int cnt = 0; fr (a1, 0, 10) { fr (a2, 0, 10) { fr (a3, 0, 10) { fr (a4, 0, 10) { fr (a5, 0, 10) { fr (a6, 0, 10) { if (a1 + a2 + a3 + a4 + a5 + a6 <= 10) { // cnt++; res.pb({a1, a2, a3, a4, a5, a6}); } } } } } } } // cout << cnt << "\n"; // // return 0; cin >> n >> k >> c; fr (i, 1, n) { fr (j, 1, k) { cin >> a[i][j]; } } if (n > 40 && k > 2) { fe (cur, res) { fr (i, k, 5) { cur[i] = 0; } } sort(all(res)); res.erase(unique(all(res)), res.end()); sort(all(res), [](array<int, 6> a, array<int, 6> b) { int sum1 = 0; fr (i, 0, k - 1) sum1 += a[i]; int sum2 = 0; fr (i, 0, k - 1) sum2 += a[i]; return sum1 > sum2; }); rf (j, sz(res) - 1, 0) { fr (i, 1, k) { need[i] = res[j][i - 1]; } ve<int> have; fr (i, 1, n) { bool bad = 0; fr (j, 1, k) { if (a[i][j] > need[j]) { bad = 1; break; } } if (!bad) { int mask = 0; fr (j, 1, k) { if (a[i][j] == need[j]) { mask |= pw(j - 1); } } have.pb(mask); } } fr (mask, 0, 63) { fr (take, 0, k) { dp[take][mask] = 0; } } dp[0][0] = 1; fe (cur, have) { rf (was, k - 1, 0) { fr (mask, 0, pw(k) - 1) { dp[was + 1][mask | cur] += dp[was][mask]; } } } c -= dp[k][pw(k) - 1]; if (c <= 0) { int sum = 0; fr (i, 1, k) sum += need[i]; cout << sum << "\n"; return 0; } } assert(0); return 0; } rec(); sort(all(scores)); reverse(all(scores)); cout << scores[c - 1] << "\n"; return 0; }

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:91:9: warning: unused variable 'cnt' [-Wunused-variable]
   91 |     int cnt = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...