Submission #8836186


Source Code Expand

Copy
import std.stdio : readln, writeln;
import std.string : split;
import std.conv : to;
import std.algorithm : sort;
import std.container : Array, BinaryHeap, RedBlackTree;
import std.typecons : Tuple;

void main()
{
    long X, Y, Z, K;
    {
        auto tmp = readln().split().to!(long[])();
        X = tmp[0];
        Y = tmp[1];
        Z = tmp[2];
        K = tmp[3];
    }
    auto A = readln().split().to!(long[])();
    auto B = readln().split().to!(long[])();
    auto C = readln().split().to!(long[])();
    A.sort!"b<a"();
    B.sort!"b<a"();
    C.sort!"b<a"();

    alias vec3 = Tuple!(long, long, long);

    bool eval(vec3 a, vec3 b)
    {
        return A[a[0]] + B[a[1]] + C[a[2]] < A[b[0]] + B[b[1]] + C[b[2]];
    }

    auto PQ = BinaryHeap!(Array!vec3, eval)();
    PQ.insert(vec3(0, 0, 0));

    auto set = new RedBlackTree!vec3();
    set.insert(vec3(0, 0, 0));

    foreach (_; 0 .. K)
    {
        auto v = PQ.front;
        PQ.removeFront();

        writeln(A[v[0]] + B[v[1]] + C[v[2]]);

        if (v[0] + 1 < X && vec3(v[0] + 1, v[1], v[2]) !in set)
        {
            PQ.insert(vec3(v[0] + 1, v[1], v[2]));
            set.insert(vec3(v[0] + 1, v[1], v[2]));
        }

        if (v[1] + 1 < Y && vec3(v[0], v[1] + 1, v[2]) !in set)
        {
            PQ.insert(vec3(v[0], v[1] + 1, v[2]));
            set.insert(vec3(v[0], v[1] + 1, v[2]));
        }

        if (v[2] + 1 < Z && vec3(v[0], v[1], v[2] + 1) !in set)
        {
            PQ.insert(vec3(v[0], v[1], v[2] + 1));
            set.insert(vec3(v[0], v[1], v[2] + 1));
        }
    }
}

Submission Info

Submission Time
Task D - Cake 123
User kotet
Language D (DMD64 v2.070.1)
Score 400
Code Size 1650 Byte
Status
Exec Time 9 ms
Memory 2940 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 400 / 400 in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
in01.txt 7 ms 636 KB
in02.txt 7 ms 636 KB
in03.txt 7 ms 636 KB
in04.txt 7 ms 636 KB
in05.txt 7 ms 636 KB
in06.txt 7 ms 636 KB
in07.txt 6 ms 636 KB
in08.txt 6 ms 636 KB
in09.txt 7 ms 636 KB
in10.txt 6 ms 636 KB
in11.txt 6 ms 636 KB
in12.txt 6 ms 636 KB
in13.txt 8 ms 892 KB
in14.txt 8 ms 892 KB
in15.txt 7 ms 764 KB
in16.txt 1 ms 256 KB
in17.txt 1 ms 256 KB
in18.txt 9 ms 1020 KB
in19.txt 9 ms 1020 KB
in20.txt 9 ms 1020 KB
in21.txt 8 ms 764 KB
in22.txt 8 ms 892 KB
in23.txt 9 ms 2940 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB