小挖的买花

Luogu

IDLGP8548

Time1000ms

Memory512MB

DifficultyP4

动态规划 DP背包 DP

花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无论如何都无法满足新鲜程度总和大于等于 $f_j$ 的要求，输出 $0$。小挖一共要让你买 $q$ 次花，你能否正确回答 ta 的问题呢？询问彼此独立。 ## Input 第 $1$ 行，共两个正整数 $n,q$。第 $2\sim n+1$ 行，每行三个正整数 $cost_i,fr_i,be_i$，分别表示一株花的三个属性。第 $n+2\sim n+q+1$ 行，每行两个正整数 $c_j,f_j$，表示每次买花时的要求。 ## Output 共 $q$ 行，每行一个整数，表示美丽度总和的最大值。如果无解，输出 $0$。 [samples] ## Background 小挖喜欢买花，但是 ta 太懒了！所以这个任务全权交给了你。 ## Note 对于 $20\%$ 的数据，$3\leq n,q\leq 16$。对于 $40\%$ 的数据，$3\leq n,q\leq 30$，$0\leq c_j,f_j\leq 50$。对于 $60\%$ 的数据，$3\leq n\leq 100$，$1\leq q\leq 5\times 10^4$，$0\leq cost_i,fr_i,c_j,f_j\leq 100$。对于另外 $20\%$ 的数据，对于每次买花，都有 $f_j=0$。对于 $100\%$ 的数据，$3\leq n\leq 500$，$\boldsymbol{1\leq q\leq 10^6}$，$0\leq cost_i,fr_i,c_j,f_j\leq 500$，$1\leq be_i \leq 10^6$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "小挖的买花",
    "description": {
      "content": "花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。 小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8548"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。\n\n小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments