Submission #70802179

---

Source Code Expand

function main(stdin) {
  // eslint-disable-next-line unused-imports/no-unused-vars, no-unused-vars
  const { next, nextstr, nextbig, nexts, nextssort, nextm, xArray } = makeInputReader(stdin)
  const n = next()
  const W = []
  const H = []
  const B = []
  for (let i = 0; i < n; i++) {
    const [w, h, b] = nexts(3)
    W.push(w)
    H.push(h)
    B.push(b)
  }
  const wSum = W.reduce((prev, curr) => prev + curr, 0)
  const offset = wSum
  // d = b - h, d >= 0
  // dp[i][d] = happy
  // const dp = Array.from({ length: n }, () => Array.from({ length: 2 * wSum + 1 }, () => -Infinity))
  let dp = new Map()
  // dp[i+1][d+w] = max()
  dp.set(offset + W[0], B[0])
  dp.set(offset - W[0], H[0])
  // dp[0][offset + W[0]] = B[0]
  // dp[0][offset - W[0]] = H[0]
  for (let i = 1; i < n; i++) {
    const next = new Map()
    const w = W[i]
    const h = H[i]
    const b = B[i]
    for (const [j, val] of dp.entries()) {
      // 放身体
      next.set(j + w, Math.max(next.get(j + w) ?? -Infinity, val + b))
      next.set(j - w, Math.max(next.get(j - w) ?? -Infinity, val + h))
    }
    dp = next
  }
  let res = -Infinity
  for (const [j, val] of dp.entries()) {
    if (j >= offset)
      res = Math.max(res, val)
  }
  return res
}
function makeInputReader(input) {
  const cin = input.trim().split(/ |\n/)
  let cid = 0
  function createNDArray(shape, fillFn) {
    if (shape.length === 0)
      return fillFn()
    const [dim, ...rest] = shape
    return Array.from({ length: dim }, () => createNDArray(rest, fillFn))
  }
  return {
    next: () => Number(cin[cid++]),
    nextstr: () => cin[cid++],
    nextbig: () => BigInt(cin[cid++]),
    nexts: (n, addNum = 0, parse = true) =>
      parse ? cin.slice(cid, cid += n).map(s => Number(s) + addNum) : cin.slice(cid, cid += n),
    nextssort: (n, parse = true, desc = false) =>
      parse
        ? cin.slice(cid, cid += n).map(Number).sort((a, b) => desc ? b - a : a - b)
        : cin.slice(cid, cid += n).sort((a, b) => desc ? b.localeCompare(a) : a.localeCompare(b)),
    nextm: (h, w, parse = true) => {
      const res = []
      for (let i = 0; i < h; i++) {
        const row = cin.slice(cid, cid += w)
        res.push(parse ? row.map(Number) : row)
      }
      return res
    },
    xArray: createNDArray,
  }
}
if (require.main === module) {
  const fs = require('node:fs')
  const input = fs.readFileSync('/dev/stdin', 'utf8')
  console.log(main(input))
}
module.exports = { main }

Submission Info

Judge Result