Submission #8899582


Source Code Expand

Copy
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

enum MAX = 1_000_100;
ulong MOD = 1_000_000_007;
ulong INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias Pair = Tuple!(long, "one", long, "two", long, "three");
alias Cake = Tuple!(long, "sum", Pair, "p");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    long x, y, z, k, cnt;
    scan(x, y, z, k);
    auto a = aryread();
    auto b = aryread();
    auto c = aryread();
    a.sort!"a>b"(), b.sort!"a>b"(), c.sort!"a>b"();
    PQueue!(Cake, "a.sum < b.sum") pq;
    bool[Pair] pairs;
    auto ans = new long[](k);

    pq.insert(Cake(a[0] + b[0] + c[0], Pair(0, 0, 0)));
    while (cnt < k)
    {
        long s = pq.front.p.one, t = pq.front.p.two, u = pq.front.p.three;
        ans[cnt] = pq.front.sum;
        pq.removeFront();
        if (s + 1 < x && !(Pair(s + 1, t, u) in pairs))
        {
            pq.insert(Cake(a[s + 1] + b[t] + c[u], Pair(s + 1, t, u)));
            pairs[Pair(s + 1, t, u)] = true;
        }
        if (t + 1 < y && !(Pair(s, t + 1, u) in pairs))
        {
            pq.insert(Cake(a[s] + b[t + 1] + c[u], Pair(s, t + 1, u)));
            pairs[Pair(s, t + 1, u)] = true;
        }
        if (u + 1 < z && !(Pair(s, t, u + 1) in pairs))
        {
            pq.insert(Cake(a[s] + b[t] + c[u + 1], Pair(s, t, u + 1)));
            pairs[Pair(s, t, u + 1)] = true;
        }
        cnt++;
    }
    foreach (e; ans)
        e.writeln();
}

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

Submission Info

Submission Time
Task D - Cake 123
User Coleball
Language D (DMD64 v2.070.1)
Score 400
Code Size 2070 Byte
Status
Exec Time 8 ms
Memory 3324 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 6 ms 764 KB
in02.txt 7 ms 2556 KB
in03.txt 6 ms 764 KB
in04.txt 6 ms 764 KB
in05.txt 6 ms 764 KB
in06.txt 6 ms 764 KB
in07.txt 6 ms 764 KB
in08.txt 6 ms 764 KB
in09.txt 6 ms 764 KB
in10.txt 5 ms 764 KB
in11.txt 5 ms 764 KB
in12.txt 5 ms 764 KB
in13.txt 6 ms 892 KB
in14.txt 6 ms 892 KB
in15.txt 5 ms 892 KB
in16.txt 1 ms 256 KB
in17.txt 1 ms 256 KB
in18.txt 7 ms 2812 KB
in19.txt 7 ms 1532 KB
in20.txt 8 ms 3324 KB
in21.txt 6 ms 892 KB
in22.txt 7 ms 892 KB
in23.txt 7 ms 1020 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB