Submission #1061653


Source Code Expand

/+ dub.sdl:
    name "A"
    dependency "dcomp" version=">=0.4.0"
+/

import std.stdio, std.algorithm, std.conv, std.range;
import std.typecons, std.math;

// import dcomp.scanner, dcomp.functional;

int U;
long[2][] d;
long[][][] dp;
bool[][][] used;

long calcBase(int p, int a, int c) {
    if (p == d.length) return 0;
    long[2] nw = d[p];
    int b = p-a;
 
    long ans = 10L^^18;
    if (c == 0) {
        ans = min(ans, U*(nw[0]+nw[1]) + calc(p+1, a, 1));
    }
    if (a < U) {
        ans = min(ans, a*(nw[0]+nw[1]) + nw[1] + calc(p+1, a+1, c));
    }
    if (b < U) {
        ans = min(ans, b*(nw[0]+nw[1]) + nw[0] + calc(p+1, a, c));
    }
    return ans;
}

memoCont!calcBase calc;

int main() {
    calc.init([[0, 5005], [0,5005], [0, 1]]);
//    dp = new long[][][](2, 5005, 2505);
//    used = new bool[][][](2, 5005, 2505);
    auto sc = new Scanner(stdin);
    int n;
    sc.read(n);
    d = new long[2][n];
    foreach (i; 0..n) {
        sc.read(d[i]);
    }
    d.sort!"a[0]+a[1] > b[0]+b[1]";
    U = n/2;
    writeln(calc(0, 0, 1-n%2));
    return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

class Scanner {
    import std.stdio : File;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f) {
        this.f = f;
    }
    string[] buf;
    private bool succ() {
        while (!buf.length) {
            if (f.eof) return false;
            buf = f.readln.split;
        }
        return true;
    }
    private bool readSingle(T)(ref T x) {
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                //string or char[10] etc
                x = buf.front;
                buf.popFront;
            } else {
                static if (isStaticArray!T) {
                    //static
                    assert(buf.length == T.length);
                }
                x = buf.map!(to!E).array;
                buf.length = 0;                
            }
        } else {
            x = buf.front.to!T;
            buf.popFront;            
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}

unittest {
    import std.path : buildPath;
    import std.file : tempDir;
    import std.algorithm : equal;
    import std.stdio : File;
    string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
    auto fout = File(fileName, "w");
    fout.writeln("1 2 3");
    fout.writeln("ab cde");
    fout.writeln("1.0 1.0 2.0");
    fout.close;
    Scanner sc = new Scanner(File(fileName, "r"));
    int a;
    int[2] b;
    char[2] c;
    string d;
    double e;
    double[] f;
    sc.read(a, b, c, d, e, f);
    assert(a == 1);
    assert(equal(b[], [2, 3]));
    assert(equal(c[], "ab"));
    assert(equal(d, "cde"));
    assert(e == 1.0);
    assert(equal(f, [1.0, 2.0]));
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/functional.d */
// module dcomp.functional;

struct memoCont(alias pred) {
    import std.range, std.algorithm, std.conv;
    import std.string : join;
    import std.traits : ReturnType, ParameterTypeTuple, isIntegral;
    import std.typecons : tuple, Tuple;
    import std.meta;
    alias R = ReturnType!pred;
    alias Args = ParameterTypeTuple!pred;
    static assert (allSatisfy!(isIntegral, Args));
    static immutable N = Args.length;
    int[2][N] rng;
    int[N] len;
    R[] dp;
    bool[] used;
    void init(int[2][N] rng) {
        this.rng = rng;
        len = rng[].map!(a => a[1]-a[0]+1).array;
        
        int sz = len.reduce!"a*b";
        dp = new R[sz];
        used = new bool[sz];
    }
    R opCall(Args args) {
        int idx, base = 1;
        foreach (i, v; args) {
            assert(rng[i][0] <= v && v <= rng[i][1]);
            idx += base*(v - rng[i][0]);
            base *= len[i];
        }
        if (used[idx]) return dp[idx];
        used[idx] = true;
        auto r = pred(args);
        dp[idx] = r;
        return r;
    }
}

unittest {
//     import dcomp.numeric.primitive;
//     import dcomp.numeric.modint;
    alias Mint = ModInt!(10^^9+7);
    auto fact = factTable!Mint(100);
    auto iFac = invFactTable!Mint(100);
    Mint C0(int a, int b) {
        if (a < 0 || a < b) return Mint(0);
        return fact[a]*iFac[b]*iFac[a-b];
    }
    struct A {
        static memoCont!C1base C1;
        static Mint C1base(int a, int b) {
            if (a == 0) {
                if (b == 0) return Mint(1);
                return Mint(0);
            }
            if (b < 0) return Mint(0);
            return C1(a-1, b-1) + C1(a-1, b);
        }
    }
    A.C1.init([[0, 100], [-2, 100]]);
    foreach (i; 0..100) {
        foreach (j; 0..100) {
            assert(C0(i, j) == A.C1(i, j));
        }
    }
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric/modint.d */
// module dcomp.numeric.modint;

// import dcomp.numeric.primitive;

struct ModInt(uint MD) if (MD < int.max) {
    import std.conv : to;
    uint v;
    this(int v) {this.v = (long(v)%MD+MD)%MD;}
    this(long v) {this.v = (v%MD+MD)%MD;}
    auto normS(uint x) {return (x<MD)?x:x-MD;}
    auto make(uint x) {ModInt m; m.v = x; return m;}
    auto opBinary(string op:"+")(ModInt r) {return make(normS(v+r.v));}
    auto opBinary(string op:"-")(ModInt r) {return make(normS(v+MD-r.v));}
    auto opBinary(string op:"*")(ModInt r) {return make( (long(v)*r.v%MD).to!uint );}
    auto opBinary(string op:"/")(ModInt r) {return this*inv(r);}
    auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");}
    static ModInt inv(ModInt x) {return ModInt(extGcd!int(x.v, MD)[0]);}
    string toString() {return v.to!string;}
}

unittest {
    static assert( is(ModInt!(uint(1000000000) * 2))); //not overflow
    static assert(!is(ModInt!(uint(1145141919) * 2))); //overflow!
    alias Mint = ModInt!(10^^9+7);
    // negative check
    assert(Mint(-1).v == 10^^9 + 6);
    assert(Mint(-1L).v == 10^^9 + 6);

    Mint a = 48;
    Mint b = Mint.inv(a);
    assert(b.v == 520833337);

    Mint c = Mint(15);
    Mint d = Mint(3);
    assert((c/d).v == 5);
}

struct DModInt {
    import std.conv : to;
    uint MD, v;
    this(int v, uint md) {
        MD = md;
        this.v = ((long(v)%MD+MD)%MD).to!uint;
    }
    this(long v, uint md) {
        MD = md;
        this.v = ((v%MD+MD)%MD).to!uint;
    }
    auto normS(uint x) {return (x<MD)?x:x-MD;}
    auto make(uint x) {DModInt m; m.MD = MD; m.v = x; return m;}
    auto opBinary(string op:"+")(DModInt r) {
        assert(MD == r.MD);
        return make(normS(v+r.v));
    }
    auto opBinary(string op:"-")(DModInt r) {
        assert(MD == r.MD);
        return make(normS(v+MD-r.v));
    }
    auto opBinary(string op:"*")(DModInt r) {
        assert(MD == r.MD);
        return make((long(v)*r.v%MD).to!uint);
    }
    auto opBinary(string op:"/")(DModInt r) {
        assert(MD == r.MD);
        return this*inv(r);
    }
    auto opOpAssign(string op)(DModInt r) {return mixin ("this=this"~op~"r");}
    static DModInt inv(DModInt x) {
        return DModInt(extGcd!int(x.v, x.MD)[0], x.MD);
    }
    string toString() {return v.to!string;}
}

unittest {
    immutable MD = 10^^9 + 7;
    alias Mint = DModInt;
    //negative check
    assert(Mint(-1, MD).v == 10^^9 + 6);
    assert(Mint(-1L, MD).v == 10^^9 + 6);
    Mint a = Mint(48, MD);
    Mint b = Mint.inv(a);
    assert(b.v == 520833337);
    Mint c = Mint(15, MD);
    Mint d = Mint(3, MD);
    assert((c/d).v == 5);
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */
// module dcomp.numeric.primitive;

import std.traits;

T pow(T, U)(T x, U n) { return pow(x, n, T(1)); }
T pow(T, U)(T x, U n, T e) {
    while (n) {
        if (n & 1) e *= x;
        x *= x;
        n /= 2;
    }
    return e;
}

unittest {
    assert(pow(3, 5) == 243);
    assert(pow(3, 5, 2) == 486);
}

T lcm(T)(in T a, in T b) {
    import std.numeric : gcd;
    return a / gcd(a,b) * b;
}

unittest {
    assert(lcm(2, 4) == 4);
    assert(lcm(3, 5) == 15);
    assert(lcm(1, 1) == 1);
    assert(lcm(0, 100) == 0);
}

//a*T[0]+b*T[1]=T[2], T[2]=gcd
//todo: to binary extgcd
T[3] extGcd(T)(in T a, in T b) 
if (!isIntegral!T || isSigned!T) //unsignedはNG
{
    if (b==0) {
        return [1, 0, a];
    } else {
        auto e = extGcd(b, a%b);
        return [e[1], e[0]-a/b*e[1], e[2]];
    }
}

unittest {
    import std.numeric : gcd;
    foreach (i; 0..100) {
        foreach (j; 0..100) {
            auto e = extGcd(i, j);
            assert(e[2] == gcd(i, j));
            assert(e[0] * i + e[1] * j == e[2]);
        }
    }
}

T[] factTable(T)(size_t length) {
    import std.range : take, recurrence;
    import std.array : array;
    return T(1).recurrence!((a, n) => a[n-1]*T(n)).take(length).array;
}

// optimize
T[] invFactTable(T)(size_t length) {
    import std.range : take, recurrence;
    import std.array : array;
    return T(1).recurrence!((a, n) => a[n-1]/T(n)).take(length).array;
}

unittest {
    import std.stdio;
//     import dcomp.numeric.modint;
    alias Mint = ModInt!(10^^9 + 7);
    auto r = factTable!Mint(20);
    Mint a = 1;
    assert(r[0] == Mint(1));
    foreach (i; 1..20) {
        a *= Mint(i);
        assert(r[i] == a);
    }
    auto p = invFactTable!Mint(20);
    foreach (i; 1..20) {
        assert((r[i]*p[i]).v == 1);
    }
}

Submission Info

Submission Time
Task F - Intervals
User yosupo
Language D (LDC 0.17.0)
Score 0
Code Size 10112 Byte
Status MLE
Exec Time 716 ms
Memory 442876 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
MLE × 2
MLE × 45
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt MLE 627 ms 442748 KB
001.txt MLE 521 ms 441980 KB
002.txt MLE 621 ms 442748 KB
003.txt MLE 716 ms 442492 KB
004.txt MLE 624 ms 442748 KB
005.txt MLE 606 ms 442236 KB
006.txt MLE 620 ms 442748 KB
007.txt MLE 557 ms 442364 KB
008.txt MLE 623 ms 442748 KB
009.txt MLE 513 ms 441852 KB
010.txt MLE 623 ms 442748 KB
011.txt MLE 549 ms 442236 KB
012.txt MLE 620 ms 442748 KB
013.txt MLE 508 ms 441724 KB
014.txt MLE 622 ms 442748 KB
015.txt MLE 553 ms 441980 KB
016.txt MLE 624 ms 442748 KB
017.txt MLE 589 ms 442492 KB
018.txt MLE 620 ms 442748 KB
019.txt MLE 629 ms 442364 KB
020.txt MLE 495 ms 441468 KB
021.txt MLE 499 ms 441468 KB
022.txt MLE 623 ms 442748 KB
023.txt MLE 621 ms 442748 KB
024.txt MLE 620 ms 442748 KB
025.txt MLE 621 ms 442748 KB
026.txt MLE 620 ms 442748 KB
027.txt MLE 622 ms 442748 KB
028.txt MLE 625 ms 442748 KB
029.txt MLE 622 ms 442748 KB
030.txt MLE 622 ms 442876 KB
031.txt MLE 625 ms 442748 KB
032.txt MLE 624 ms 442748 KB
033.txt MLE 625 ms 442748 KB
034.txt MLE 625 ms 442748 KB
035.txt MLE 622 ms 442748 KB
036.txt MLE 622 ms 442748 KB
037.txt MLE 623 ms 442748 KB
038.txt MLE 620 ms 442748 KB
039.txt MLE 623 ms 442748 KB
040.txt MLE 621 ms 442748 KB
041.txt MLE 621 ms 442748 KB
042.txt MLE 623 ms 442748 KB
example0.txt MLE 500 ms 441468 KB
example1.txt MLE 499 ms 441468 KB