[NICA #1] 上大分

Luogu

IDLGB3803

Time1000ms

Memory128MB

DifficultyP3

动态规划 DP

小 T 获得了预知能力，能预知自己后面 $n$ 场比赛的表现分。下面是表现分的定义： - 记小 T 在参加这场比赛前账号的分数是 $i$，他这场的表现分为 $j$，那么打完这场之后他的账号分数是 $i+\lfloor\frac{j-i}{4}\rfloor$ 。 - 其中 $\lfloor x\rfloor$ 表示对 $x$ 下取整，如 $\lfloor 1.9\rfloor=1,\lfloor -1.3\rfloor=-2$。但是小 T 只有一个账号，初始分数是 $x$。他决定从未来的 $n$ 次比赛中选择**不超过** $k$ 次参加，同时，这些比赛的类型不同，具体分为两类，这些类型会给出： - division 1：不管小 T **当前的分数**是多少，都可以参加。 - division 2：只有小 T **当前的分数** $< 1900$，他才能参加。 - 注意，**当前的分数**为这次比赛前的分数，而不是初始分数。**当前的分数**会随着小 T 之前选择参加比赛的策略变动而变动。他希望自己在所有比赛结束后得分最高，请你来帮他规划一下，在最优决策下，参加完选出的比赛后能获得的最高分数是多少。 ## Input 第一行三个正整数 $n,k,x$，同题意。接下来 $n$ 行每行两个整数 $\mathrm{type},a_i$，分别表示比赛的类型和小 C 这场比赛的表现分，其中 $\mathrm{type}=2$ 表示是 division 2 的比赛，$\mathrm{type}=1$ 表示是 division 1 的比赛。 ## Output 一行一个数，表示答案。 [samples] ## Background 小 T 喜欢打 CF。 ## Note #### 【样例解释 2】两场都打。 #### 【数据范围】对于 $100\%$ 的数据，满足 $0\leq x,a_i\leq 4000$，$n,k\leq 5000$，$1\leq k\leq n$。

Samples

Input #1

2 2 1900
2 1899
2 4000

Output #1

Input #2

2 2 1900
1 1899
2 4000

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[NICA #1] 上大分",
    "description": {
      "content": "小 T 获得了预知能力，能预知自己后面 $n$ 场比赛的表现分。 下面是表现分的定义： - 记小 T 在参加这场比赛前账号的分数是 $i$，他这场的表现分为 $j$，那么打完这场之后他的账号分数是 $i+\\lfloor\\frac{j-i}{4}\\rfloor$ 。 - 其中 $\\lfloor x\\rfloor$ 表示对 $x$ 下取整，如 $\\lfloor 1.9\\rfloor=1,\\lflo",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3803"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 T 获得了预知能力，能预知自己后面 $n$ 场比赛的表现分。\n\n下面是表现分的定义：\n\n- 记小 T 在参加这场比赛前账号的分数是 $i$，他这场的表现分为 $j$，那么打完这场之后他的账号分数是 $i+\\lfloor\\frac{j-i}{4}\\rfloor$ 。\n- 其中 $\\lfloor x\\rfloor$ 表示对 $x$ 下取整，如 $\\lfloor 1.9\\rfloor=1,\\lflo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments