Submission #15426815


Source Code Expand

Copy
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on
void main()
{
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long[] A = new long[](cast(size_t)(N));
    foreach (i; 0 .. cast(size_t)(N))
    {
        A[i] = input.front.to!long;
        input.popFront;
    }

    solve(N, A);
}

void solve(long N, long[] A)
{
    auto dp = new long[long][](N + 1);
    dp[0][1000] = 0;
    foreach (i; 0 .. N)
    {
        foreach (key, val; dp[i])
        {
            dp[i + 1][key] = dp[i + 1].get(key, 0).max(val);
            dp[i + 1][key % A[i]] = dp[i + 1].get(key % A[i], 0).max(val + key / A[i]);
            dp[i + 1][key + val * A[i]] = dp[i + 1].get(key + val * A[i], 0).max(0);
        }
    }
    writeln(dp[N].keys.reduce!max);
}

Submission Info

Submission Time
Task D - Road to Millionaire
User kotet
Language D (DMD 2.091.0)
Score 400
Code Size 1292 Byte
Status AC
Exec Time 135 ms
Memory 34592 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status AC
AC × 21
Set Name Test Cases
Sample
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-random-01.txt, 01-random-02.txt, 01-random-03.txt, 01-random-04.txt, 01-random-05.txt, 01-random-06.txt, 01-random-07.txt, 01-random-08.txt, 01-random-09.txt, 01-random-10.txt, 02-increasing-01.txt, 03-decreasing-01.txt, 04-large-01.txt, 04-large-02.txt, 04-large-03.txt, 05-maximum-01.txt, 05-maximum-02.txt, 05-maximum-03.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 6 ms 3760 KB
00-sample-02.txt AC 2 ms 3552 KB
00-sample-03.txt AC 4 ms 3556 KB
01-random-01.txt AC 2 ms 3524 KB
01-random-02.txt AC 2 ms 3592 KB
01-random-03.txt AC 41 ms 8164 KB
01-random-04.txt AC 76 ms 20780 KB
01-random-05.txt AC 127 ms 31916 KB
01-random-06.txt AC 83 ms 22132 KB
01-random-07.txt AC 32 ms 6408 KB
01-random-08.txt AC 27 ms 5840 KB
01-random-09.txt AC 6 ms 3584 KB
01-random-10.txt AC 2 ms 3760 KB
02-increasing-01.txt AC 28 ms 5960 KB
03-decreasing-01.txt AC 11 ms 4212 KB
04-large-01.txt AC 106 ms 27596 KB
04-large-02.txt AC 122 ms 31924 KB
04-large-03.txt AC 135 ms 34592 KB
05-maximum-01.txt AC 9 ms 3752 KB
05-maximum-02.txt AC 15 ms 4944 KB
05-maximum-03.txt AC 8 ms 3920 KB