Submission #62301207

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll = long long;
using ii = pair<uint32_t, uint32_t>;
#ifdef ONLINE_JUDGE
#define cerr \
    if (false) cerr  // Disable cerr output by making it an empty statement
#endif
#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << '\n';
#define INT(...)     \
    int __VA_ARGS__; \
    IN(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>

#include <queue>

using namespace std;

using ll = long long;
using ii = pair<uint32_t, uint32_t>;

#ifdef ONLINE_JUDGE
#define cerr \
    if (false) cerr  // Disable cerr output by making it an empty statement
#endif

#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << '\n';

#define INT(...)     \
    int __VA_ARGS__; \
    IN(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    IN(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    IN(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    IN(__VA_ARGS__)
#define DBL(...)             \
    long double __VA_ARGS__; \
    IN(__VA_ARGS__)

#define VEC(type, name, size) \
    vector<type> name(size);  \
    read(name)
#define VV(type, name, h, w)                       \
    vector<vector<type>> name(h, vector<type>(w)); \
    read(name)

void read(int &a) { cin >> a; }
void read(unsigned int &a) { cin >> a; }
void read(long long &a) { cin >> a; }
void read(char &a) { cin >> a; }
void read(double &a) { cin >> a; }
void read(long double &a) { cin >> a; }
void read(string &a) { cin >> a; }
template <class T, class S>
void read(pair<T, S> &p) {
    read(p.first), read(p.second);
}
template <typename... Args>
void read(tuple<Args...> &t) {
    apply([&](auto &...xs) { (read(xs), ...); }, t);
}
template <class T>
void read(vector<T> &a) {
    for (auto &i : a) read(i);
}
template <class T>
void read(T &a) {
    cin >> a;
}

void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
    read(head);
    IN(tail...);
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
    os << A.first << " " << A.second;
    return os;
}

template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    apply(
        [&os](const auto &...xs) {
            size_t n = 0;
            ((os << (n++ ? " " : "") << xs), ...);
        },
        t);
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        if (i) os << " ";
        os << A[i];
    }
    return os;
}

class CoutInitializer {
   public:
    CoutInitializer() { std::cout << std::fixed << std::setprecision(15); }
};
static CoutInitializer cout_initializer;

void print() {
    cout << "\n";
    cout.flush();
}

template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << " ";
    print(forward<Tail>(tail)...);
}

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }

ll safe_mul(int a, int b, int c) { return 1LL * a * b + 1LL * b * c + 1LL * a * c; }

std::string int128ToString(__int128 value) {
    if (value == 0) return "0";
    bool isNegative = value < 0;
    if (isNegative) value = -value;
    std::string result;
    while (value > 0) {
        result = char('0' + (value % 10)) + result;
        value /= 10;
    }
    if (isNegative) result = '-' + result;
    return result;
}

ll store(ll a, ll b, int c) { return (a << 40) | (b << 20) | c; }

tuple<int, int, int> retrieve(ll v) {
    return {(v >> 40) & 0xFFFFF, (v >> 20) & 0xFFFFF, (v & 0xFFFFF)};
}

void solve() {
    INT(n, k);
    VV(ll, mat, 3, n);
    for (int ctr1 = 0; ctr1 < 3; ++ctr1) ranges::sort(mat[ctr1]);

    priority_queue<pair<ll, ll>> pq;
    pq.emplace(safe_mul(mat[0][n - 1], mat[1][n - 1], mat[2][n - 1]), store(n - 1, n - 1, n - 1));
    int order = 0;
    set<ll> done;
    while (!pq.empty()) {
        auto [nxt, bm] = pq.top();
        pq.pop();
        if (++order == k) {
            cout << nxt << '\n';
            return;
        }
        auto [x, y, z] = retrieve(bm);
        vector<int> cur = {x, y, z};
        ll bm1 = store(x - 1, y, z);
        if (x - 1 >= 0 && !done.count(bm1)) {
            pq.emplace(safe_mul(mat[0][x - 1], mat[1][y], mat[2][z]), bm1);
            done.insert(bm1);
        }
        bm1 = store(x, y - 1, z);
        if (y - 1 >= 0 && !done.count(bm1)) {
            pq.emplace(safe_mul(mat[0][x], mat[1][y - 1], mat[2][z]), bm1);
            done.insert(bm1);
        }
        bm1 = store(x, y, z - 1);
        if (z - 1 >= 0 && !done.count(bm1)) {
            pq.emplace(safe_mul(mat[0][x], mat[1][y], mat[2][z - 1]), bm1);
            done.insert(bm1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;

    while (t--) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result