結果

問題 No.2686 商品券の使い道
ユーザー 👑 seekworserseekworser
提出日時 2024-03-21 10:10:50
言語 Nim
(2.0.2)
結果
WA  
実行時間 -
コード長 9,012 bytes
コンパイル時間 4,307 ms
コンパイル使用メモリ 74,612 KB
実行使用メモリ 21,260 KB
最終ジャッジ日時 2024-03-21 10:11:00
合計ジャッジ時間 9,095 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 27 ms
10,112 KB
testcase_11 AC 33 ms
10,112 KB
testcase_12 AC 30 ms
10,112 KB
testcase_13 AC 31 ms
10,112 KB
testcase_14 AC 32 ms
10,112 KB
testcase_15 AC 31 ms
10,112 KB
testcase_16 AC 32 ms
10,112 KB
testcase_17 AC 31 ms
10,112 KB
testcase_18 AC 31 ms
10,112 KB
testcase_19 AC 31 ms
10,112 KB
testcase_20 AC 31 ms
10,112 KB
testcase_21 AC 33 ms
10,112 KB
testcase_22 AC 30 ms
10,112 KB
testcase_23 AC 31 ms
10,112 KB
testcase_24 AC 33 ms
10,112 KB
testcase_25 AC 28 ms
10,112 KB
testcase_26 AC 31 ms
10,112 KB
testcase_27 AC 32 ms
10,112 KB
testcase_28 AC 28 ms
10,112 KB
testcase_29 AC 87 ms
21,260 KB
testcase_30 AC 91 ms
21,260 KB
testcase_31 AC 92 ms
21,260 KB
testcase_32 AC 92 ms
21,260 KB
testcase_33 AC 96 ms
21,260 KB
testcase_34 AC 89 ms
21,260 KB
testcase_35 AC 93 ms
21,260 KB
testcase_36 AC 95 ms
21,260 KB
testcase_37 AC 93 ms
21,260 KB
testcase_38 AC 90 ms
21,260 KB
testcase_39 AC 93 ms
21,260 KB
testcase_40 AC 93 ms
21,260 KB
testcase_41 AC 76 ms
21,260 KB
testcase_42 AC 95 ms
21,260 KB
testcase_43 AC 94 ms
21,260 KB
testcase_44 AC 96 ms
21,260 KB
testcase_45 AC 96 ms
21,260 KB
testcase_46 AC 97 ms
21,260 KB
evil_random20_1.txt WA -
evil_random20_2.txt WA -
evil_random20_3.txt WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# verification-helper: PROBLEM https://yukicoder.me/problems/no/2686
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc ii(): int {.inline.} = scanf("%lld\n", addr result)
include sequtils
include strutils
include algorithm
include sugar
ImportExpand "cplib/collections/segtree.nim" <=== "when not declared CPLIB_COLLECTIONS_SEGTREE:\n    const CPLIB_COLLECTIONS_SEGTREE* = 1\n    import algorithm\n    type SegmentTree*[T] = ref object\n        default: T\n        merge: proc(x: T, y: T): T\n        arr*: seq[T]\n        lastnode: int\n        length: int\n    proc initSegmentTree*[T](v: seq[T], merge: proc(x: T, y: T): T, default: T): SegmentTree[T] =\n        ## セグメントツリーを生成します。\n        ## vに元となるリスト、mergeに二つの区間をマージする関数、デフォルトに単位元を与えてください。\n        var lastnode = 1\n        while lastnode < len(v):\n            lastnode*=2\n        var arr = newSeq[T](2*lastnode)\n        arr.fill(default)\n        var self = SegmentTree[T](default: default, merge: merge, arr: arr, lastnode: lastnode, length: len(v))\n        #1-indexedで作成する\n        for i in 0..<len(v):\n            self.arr[self.lastnode+i] = v[i]\n        for i in countdown(lastnode-1, 1):\n            self.arr[i] = self.merge(self.arr[2*i], self.arr[2*i+1])\n        return self\n\n    proc update*[T](self: SegmentTree[T], x: Natural, val: T) =\n        ## xの要素をvalに変更します。\n        assert x < self.length\n        var x = x\n        x += self.lastnode\n        self.arr[x] = val\n        while x > 1:\n            x = x shr 1\n            self.arr[x] = self.merge(self.arr[2*x], self.arr[2*x+1])\n    proc get*[T](self: SegmentTree[T], q_left: Natural, q_right: Natural): T =\n        ## 半解区間[q_left,q_right)についての演算結果を返します。\n        assert q_left <= q_right and 0 <= q_left and q_right <= self.length\n        var q_left = q_left\n        var q_right = q_right\n        q_left += self.lastnode\n        q_right += self.lastnode\n        var (lres, rres) = (self.default, self.default)\n        while q_left < q_right:\n            if (q_left and 1) > 0:\n                lres = self.merge(lres, self.arr[q_left])\n                q_left += 1\n            if (q_right and 1) > 0:\n                q_right -= 1\n                rres = self.merge(self.arr[q_right], rres)\n            q_left = q_left shr 1\n            q_right = q_right shr 1\n        return self.merge(lres, rres)\n    proc get*[T](self: SegmentTree[T], segment: HSlice[int, int]): T =\n        assert segment.a <= segment.b + 1 and 0 <= segment.a and segment.b+1 <= self.length\n        return self.get(segment.a, segment.b+1)\n    proc `[]`*[T](self: SegmentTree[T], index: Natural): T =\n        assert index < self.length\n        return self.arr[index+self.lastnode]\n    proc `[]=`*[T](self: SegmentTree[T], index: Natural, val: T) =\n        assert index < self.length\n        self.update(index, val)\n    proc get_all*[T](self: SegmentTree[T]): T =\n        ## [0,len(self))区間の演算結果をO(1)で返す\n        return self.arr[1]\n    proc len*[T](self: SegmentTree[T]): int =\n        return self.length\n\n    template newSegWith*(V, merge, default: untyped): untyped =\n        initSegmentTree(V, (l, r{.inject.}: typeof(default)) => merge, default)\n\n"
ImportExpand "cplib/collections/hashtable.nim" <=== "when not declared CPLIB_COLLECTIONS_HASHTABLE:\n    const CPLIB_COLLECTIONS_HASHTABLE* = 1\n    import bitops\n    import sequtils\n    import hashes\n    type State = enum\n        empty, active, inactive\n    type Node[K, V] = object\n        state: State\n        value: (K, V)\n    type HashTable*[K, V] = object\n        values*: seq[Node[K, V]]\n        len: int\n        fill: int\n        mask: int\n    proc vlen(x: int): int = (if x == 0: 4 else: 1 shl (fastLog2(x) + 2))\n    proc len*[K, V](self: HashTable[K, V]): int = self.len\n    proc initHashTable*[K, V](): HashTable[K, V] =\n        var vlen = 4\n        return HashTable[K, V](values: newSeqWith(vlen, Node[K, V](state: State.empty)), len: 0, fill: 0, mask: vlen - 1)\n    proc initHashTable*[K, V](capacity: int): HashTable[K, V] =\n        var vlen = capacity.vlen\n        return HashTable[K, V](values: newSeqWith(vlen, Node[K, V](state: State.empty)), len: 0, fill: 0, mask: vlen - 1)\n    iterator pairs*[K, V](self: HashTable[K, V]): (K, V) =\n        for item in self.values:\n            if item.state == State.active: yield item.value\n    iterator keys*[K, V](self: HashTable[K, V]): K =\n        for item in self.values:\n            if item.state == State.active: yield item.value[0]\n    iterator values*[K, V](self: HashTable[K, V]): V =\n        for item in self.values:\n            if item.state == State.active: yield item.value[1]\n    proc find[K, V](self: HashTable[K, V], x: K): int =\n        var sh: int = hash(x) and self.mask\n        while self.values[sh].state != State.empty and self.values[sh].value[0] != x:\n            sh = (sh + 1) and self.mask\n        return sh\n    proc add_item[K, V](self: var HashTable[K, V], key: K, val: V) =\n        var pos = self.find(key)\n        if self.values[pos].state == State.active:\n            self.values[pos].value[1] = val\n            return\n        self.len += 1\n        self.fill += 1\n        self.values[pos].value = (key, val)\n        self.values[pos].state = State.active\n    proc resize[K, V](self: var HashTable[K, V]) =\n        var vlen = self.len.vlen\n        var vi = newSeq[Node[K, V]](vlen)\n        self.mask = vlen - 1\n        self.len = 0\n        self.fill = 0\n        swap(vi, self.values)\n        for item in vi:\n            if item.state == State.empty: continue\n            var (key, val) = item.value\n            self.add_item(key, val)\n    proc incl*[K, V](self: var HashTable[K, V], val: (K, V)) =\n        self.add_item(val)\n        if self.fill.vlen > self.values.len: self.resize\n        # if self.fill > self.values.len div HASHSET_INCL_RESIZE_RATIO: self.resize\n    proc contains*[K, V](self: var HashTable[K, V], key: K): bool = (self.values[self.find(key)].state == State.active)\n    proc hasKey*[K, V](self: var HashTable[K, V], key: K): bool = self.contains(key)\n    proc `[]`*[K, V](self: HashTable[K, V], key: K): V =\n        var pos = self.find(key)\n        assert self.values[pos].state == State.active, \"Key \\\"\" & $key & \"\\\" not found\"\n        return self.values[pos].value[1]\n    proc `[]`*[K, V](self: var HashTable[K, V], key: K): var V =\n        var pos = self.find(key)\n        assert self.values[pos].state == State.active, \"Key \\\"\" & $key & \"\\\" not found\"\n        return self.values[pos].value[1]\n    proc `[]=`*[K, V](self: var HashTable[K, V], key: K, val: V) =\n        var pos = self.find(key)\n        self.values[pos].value = (key, val)\n        self.values[pos].state = State.active\n        self.len += 1\n        self.fill += 1\n        if self.fill.vlen > self.values.len: self.resize\n    proc clear*[K, V](self: var HashTable[K, V]) = self = initHashTable[K, V]()\n    proc del*[K, V](self: var HashTable[K, V], key: K) =\n        var pos = self.find(key)\n        if self.values[pos].state != State.active: return\n        self.len -= 1\n        self.values[pos].state = State.inactive\n    proc excl*[K, V](self: var HashTable[K, V], key: K) = self.del(key)\n    proc hash*[K, V](self: HashTable[K, V]): Hash =\n        for item in self.pairs:\n            result = result !& hash(item)\n"

var n, m, q = ii()
var a, b = newSeq[int](n)
for i in 0..<n:
    a[i] = ii()
    b[i] = ii()

proc dp(a, b: seq[int]): HashTable[(int, int), int] =
    var n = a.len
    var dp = initHashTable[(int, int), int]()
    dp[(0, 0)] = 0
    for i in 0..<n:
        var dpn = dp
        for t, v in dp:
            var (x, y) = t
            if (x+a[i], y) in dpn: dpn[(x+a[i], y)] = max(dpn[(x+a[i], y)], v + b[i])
            else: dpn[(x+a[i], y)] = v + b[i]
            if (x, y+a[i]) in dpn: dpn[(x, y+a[i])] = max(dpn[(x, y+a[i])], v + b[i])
            else: dpn[(x, y+a[i])] = v + b[i]
        swap(dp, dpn)
    return dp
var dp1 = dp(a[0..<(n div 2)], b[0..<(n div 2)])
var dp2 = dp(a[(n div 2)..<n], b[(n div 2)..<n])

var c = dp2.keys.toSeq.mapIt(it[0]).sorted.deduplicate(true)
var add = newSeqWith(c.len, newSeq[(int, int)](0))
for k, v in dp2:
    var (x, y) = k
    add[c.lowerBound(x)].add((y, v))
var seg = newSegWith(newSeqWith(c.len, -1), max(l, r), -1)

var qi = dp1.pairs.toseq.mapIt((it[0][0], it[0][1], it[1])).sortedByIt(-it[0])
var ans = 0
var pos = 0
for (x, y, v) in qi:
    while pos < c.len and m - x >= c[pos]:
        for (yn, vn) in add[pos]:
            seg[c.lowerBound(yn)] = max(seg[c.lowerBound(yn)], vn)
        pos += 1
    var r = c.upperBound(q - y)
    ans = max(ans, seg.get(0..<r) + v)
echo ans
0