結果
| 問題 | No.561 東京と京都 |
| ユーザー |
 yosupot
|
| 提出日時 | 2017-08-25 22:42:23 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 8,430 bytes |
| コンパイル時間 | 1,044 ms |
| コンパイル使用メモリ | 106,412 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-12 21:44:07 |
| 合計ジャッジ時間 | 1,899 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 17 |
ソースコード
/+ dub.sdl:name "D"dependency "dcomp" version=">=0.6.0"+/import std.stdio, std.algorithm, std.range, std.conv;// import dcomp.foundation, dcomp.scanner;// import dcomp.functional;int n, d;int[2][] t;int calcBase(int day, int pos) {if (day == n) return 0;int ans = -1;ans = max(ans, t[day][pos] + calc(day+1, pos));ans = max(ans, t[day][1-pos] - d + calc(day+1, 1-pos));return ans;}memoCont!calcBase calc;int main() {auto sc = new Scanner(stdin);sc.read(n, d);t = new int[2][n];foreach (i; 0..n) {sc.read(t[i][0], t[i][1]);}calc.init([[0, 104], [0, 1]]);writeln(calc(0, 0));return 0;}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/functional.d */// module dcomp.functional;struct memoCont(alias pred) {import core.exception : RangeError;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) {version(assert) {if (v < rng[i][0] || rng[i][1] < v) {throw new RangeError;}}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;}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/modint.d */// module dcomp.modint;// import dcomp.numeric.primitive;struct ModInt(uint MD) if (MD < int.max) {import std.conv : to;uint v;this(int v) {this(long(v));}this(long v) {this.v = (v%MD+MD)%MD;}static auto normS(uint x) {return (x<MD)?x:x-MD;}static auto make(uint x) {ModInt m; m.v = x; return m;}auto opBinary(string op:"+")(ModInt r) const {return make(normS(v+r.v));}auto opBinary(string op:"-")(ModInt r) const {return make(normS(v+MD-r.v));}auto opBinary(string op:"*")(ModInt r) const {return make((long(v)*r.v%MD).to!uint);}auto opBinary(string op:"/")(ModInt r) const {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;}}struct DModInt(string name) {import std.conv : to;static uint MD;uint v;this(int v) {this(long(v));}this(long v) {this.v = ((v%MD+MD)%MD).to!uint;}static auto normS(uint x) {return (x<MD)?x:x-MD;}static auto make(uint x) {DModInt m; m.MD = MD; m.v = x; return m;}auto opBinary(string op:"+")(DModInt r) const {return make(normS(v+r.v));}auto opBinary(string op:"-")(DModInt r) const {return make(normS(v+MD-r.v));}auto opBinary(string op:"*")(DModInt r) const {return make((long(v)*r.v%MD).to!uint);}auto opBinary(string op:"/")(DModInt r) const {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, MD)[0]);}string toString() {return v.to!string;}}template isModInt(T) {const isModInt =is(T : ModInt!MD, uint MD) || is(S : DModInt!S, string s);}T[] factTable(T)(size_t length) if (isModInt!T) {import std.range : take, recurrence;import std.array : array;return T(1).recurrence!((a, n) => a[n-1]*T(n)).take(length).array;}T[] invFactTable(T)(size_t length) if (isModInt!T) {import std.algorithm : map, reduce;import std.range : take, recurrence, iota;import std.array : array;auto res = new T[length];res[$-1] = T(1) / iota(1, length).map!T.reduce!"a*b";foreach_reverse (i, v; res[0..$-1]) {res[i] = res[i+1] * T(i+1);}return res;}T[] invTable(T)(size_t length) if (isModInt!T) {auto f = factTable!T(length);auto invf = invFactTable!T(length);auto res = new T[length];foreach (i; 1..length) {res[i] = invf[i] * f[i-1];}return res;}/* IMPORT /home/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;}char[512] lineBuf;char[] line;private bool succ() {import std.range.primitives : empty, front, popFront;import std.ascii : isWhite;while (true) {while (!line.empty && line.front.isWhite) {line.popFront;}if (!line.empty) break;if (f.eof) return false;line = lineBuf[];f.readln(line);}return true;}private bool readSingle(T)(ref T x) {import std.algorithm : findSplitBefore;import std.string : strip;import std.conv : parse;if (!succ()) return false;static if (isArray!T) {alias E = ElementType!T;static if (isSomeChar!E) {auto r = line.findSplitBefore(" ");x = r[0].strip.dup;line = r[1];} else {auto buf = line.split.map!(to!E).array;static if (isStaticArray!T) {assert(buf.length == T.length);}x = buf;line.length = 0;}} else {x = line.parse!T;}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);}}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */// module dcomp.foundation;static if (__VERSION__ <= 2070) {template fold(fun...) if (fun.length >= 1) {auto fold(R, S...)(R r, S seed) {import std.algorithm : reduce;static if (S.length < 2) {return reduce!fun(seed, r);} else {import std.typecons : tuple;return reduce!fun(tuple(seed), r);}}}}version (X86) static if (__VERSION__ < 2071) {import core.bitop : bsf, bsr, popcnt;int bsf(ulong v) {foreach (i; 0..64) {if (v & (1UL << i)) return i;}return -1;}int bsr(ulong v) {foreach_reverse (i; 0..64) {if (v & (1UL << i)) return i;}return -1;}int popcnt(ulong v) {int c = 0;foreach (i; 0..64) {if (v & (1UL << i)) c++;}return c;}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */// module dcomp.numeric.primitive;import std.traits;import std.bigint;T pow(T, U)(T x, U n) if (!isFloatingPoint!T && (isIntegral!U || is(U == BigInt))) {return pow(x, n, T(1));}T pow(T, U)(T x, U n, T e) if (isIntegral!U || is(U == BigInt)) {while (n) {if (n & 1) e *= x;x *= x;n /= 2;}return e;}T lcm(T)(in T a, in T b) {import std.numeric : gcd;return a / gcd(a,b) * b;}T[3] extGcd(T)(in T a, in T b)if (!isIntegral!T || isSigned!T){if (b==0) {return [T(1), T(0), a];} else {auto e = extGcd(b, a%b);return [e[1], e[0]-a/b*e[1], e[2]];}}