[POI 2020/2021 R1] Cukiernia / 糕点店

Luogu

IDLGP9294

Time1000ms

Memory128MB

DifficultyP3

2020POI（波兰）

Bajtuś 面包店售卖蛋糕，甜甜圈和羊角面包三种食物。在面包店中，有 $n$ 个橱窗，在正常情况下，每个货架上只应该放置一种食物。但一天早上，面包店老板 Bajtazara 的儿子 Bajtuś 偷偷进入了面包店，将所有的食物摆放得乱七八糟。面包店马上就要开门了，Bajtazara 急切地想要重新摆放食物，使得每个货架上只有一种食物（特别地，一个货架上没有食物也是允许的）。请你帮助他求出，至少需要移动多少次食物才能达成目标。 ## Input 第一行一个整数 $n$，代表面包店中货架的数量。接下来 $n$ 行，第 $i$ 行三个整数 $d_i,p_i,r_i$，分别代表该货架上现有的蛋糕数，甜甜圈数和羊角面包数。数据保证面包店中至少有一份食物。 ## Output 输出一个整数，表示需要移动食物的最小次数。 [samples] ## Background **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Cukiernia](https://sio2.mimuw.edu.pl/c/oi28-1/p/cuk/)。** ## Note 【样例解释#1】：一种合法的移动方案如下： 1. 将一个甜甜圈从货架 $1$ 移动至货架 $3$，将一个羊角面包从货架 $1$ 移动至货架 $2$； 2. 将三个甜甜圈从货架 $2$ 移动至货架 $3$； 3. 将一个蛋糕从货架 $3$ 移动至货架 $1$，将三个羊角面包从货架 $3$ 移动至货架 $2$；在此之后，货架 $1$ 只有蛋糕，货架 $2$ 只有羊角面包，货架 $3$ 只有甜甜圈，货架 $4$ 只有蛋糕，货架 $5$ 是空的。【数据范围】：所有测试点均满足：$3 \leq n \leq 3 \times 10^5$，$0 \leq d_i,p_i,r_i \leq 10^9$。 | 子任务编号 | $n \leq$ | 分值 | | :----------: | :---------------: | :----: | | $1$ | $10$ | $15$ | | $2$ | $5 \times 10^3$ | $35$ | | $3$ | $3 \times 10^5$ | $50$ |

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[POI 2020/2021 R1] Cukiernia / 糕点店",
    "description": {
      "content": "Bajtuś 面包店售卖蛋糕，甜甜圈和羊角面包三种食物。在面包店中，有 $n$ 个橱窗，在正常情况下，每个货架上只应该放置一种食物。但一天早上，面包店老板 Bajtazara 的儿子 Bajtuś 偷偷进入了面包店，将所有的食物摆放得乱七八糟。 面包店马上就要开门了，Bajtazara 急切地想要重新摆放食物，使得每个货架上只有一种食物（特别地，一个货架上没有食物也是允许的）。请你帮助他求出，至",
      "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": "LGP9294"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bajtuś 面包店售卖蛋糕，甜甜圈和羊角面包三种食物。在面包店中，有 $n$ 个橱窗，在正常情况下，每个货架上只应该放置一种食物。但一天早上，面包店老板 Bajtazara 的儿子 Bajtuś 偷偷进入了面包店，将所有的食物摆放得乱七八糟。\n\n面包店马上就要开门了，Bajtazara 急切地想要重新摆放食物，使得每个货架上只有一种食物（特别地，一个货架上没有食物也是允许的）。请你帮助他求出，至...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments