Problem

矩阵

Time Limit:
Memory Limit:

Description

Input

第一行两个数、，表示矩阵的大小。
接下来行，每行列，描述矩阵。
最后一行两个数，。

Output

一行，输出最小的答案。

Problem

BZOJ3676【NOI2015】品酒大会

Time Limit:
Memory Limit:

Description

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。
在大会的晚餐上，调酒师 调制了 杯鸡尾酒。这 杯鸡尾酒排成一行，其中第 杯酒 被贴上了一个标签 ，每个标签都是 个小写英文字母之一。设 表示第 杯酒到第 杯酒的 个标签顺次连接构成的字符串。若 ，其中，，，，则称第 杯酒与第 杯酒是“ 相似”的。当然两杯“ 相似” 的酒同时也是“ 相似”、“ 相似”、……、“ 相似”的。特别地，对于任意的，第 杯酒和第 杯酒都是“ 相似”的。
在品尝环节上，品酒师 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 杯酒 的美味度为 。现在 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 杯酒与第 杯酒调兑在一起，将得到一杯美味度为 的酒。现在请各位品酒师分别对于 ，统计出有多少种方法可以选出 杯“ 相似”的酒，并回答选择 杯“相似”的酒调兑可以得到的美味度的最大值。

Input

第 行包含 个正整数 ，表示鸡尾酒的杯数。
第 行包含一个长度为 的字符串 ，其中第 i 个字符表示第 杯酒的标签。
第 行包含 个整数，相邻整数之间用单个空格隔开，其中第 个整数表示第 杯酒的美味度 。

Output

输出文件包括 行。第 行输出 个整数，中间用单个空格隔开。第 个整数表示选出两杯“ 相似”的酒的方案数，第 个整数表示选出两杯“ 相似”的酒调兑可以得到的最大美味度。若不存在两杯“ 相似”的酒，这两个数均为 。

Problem

BZOJ3676【APIO2014】回文串

Time Limit:
Memory Limit:

Description

给你一个由小写拉丁字母组成的字符串 。我们定义 的一个子串的存在值为这个子串在 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 ，求所有回文子串中的最大存在值。

Input

输入只有一行，为一个只包含小写字母的非空字符串 。

Output

输出一个整数，表示所有回文子串中的最大存在值。

Problem

Tree

Time Limit:
Memory Limit:

Description

给定个点以及每个点的权值，要你处理接下来的个操作。操作有种。操作从到编号。点从到编号。
.后接两个整数 ，代表询问从到的路径上的点的权值的和。保证到是联通的。
.后接两个整数 ，代表连接到，若x到y已经联通则无需连接。
.后接两个整数 ，代表删除边，不保证边 存在。
.后接两个整数 ，代表将点上的权值变成。

Input

第行两个整数，分别为和，代表点数和操作数。
第行到第行，每行一个整数，整数在 内，代表每个点的权值。
第行到第行，每行三个整数，分别代表操作类型和操作所需的量。

Output

对于每一个号操作，你须输出到的路径上点权的和。

高新2017联训划水记

Problem

Beauty Contest

Description

贝茜在牛的选美比赛中赢得了冠军”牛世界小姐”。因此,贝西会参观()个农场来传播善意。世界将被表示成一个二维平面,每个农场位于一对整数坐标()。没有两个农场共享相同的一对坐标。
尽管贝西沿直线前往下一个农场，但牧场之间的距离可能很大,所以她需要一个手提箱保证在每一段旅程中她有足够吃的食物。她想确定她可能需要旅行的最大可能距离,她要知道她必须带的手提箱的大小。帮助贝西计算农场的最大距离。

Input

第行一个整数，第行两个整数表示个农场中第个的坐标

Output

一行，最远距离的平方

Problem

序列

Description

给出一个长度为的正整数序列，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过 个，并且选出的元素之和最大。

Input

第行三个数。 接下来行个正整数表示。

Output

最大和。

Problem

【SHOI2003】Pacman 吃豆豆

Description

两个吃豆豆。一开始的时候，都在坐标原点的左下方，豆豆都在右上方。走到豆豆处就会吃掉它。行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个计算一下，他们俩加起来最多能吃掉多少豆豆。

Input

第一行为一个整数，表示豆豆的数目。 接下来 行，每行一对正整数，表示第个豆豆的坐标。任意两个豆豆的坐标都不会重合。

Output

仅有一行包含一个整数，即两个加起来最多能吃掉的豆豆数量

Problem

学习小组

Time Limit:
Memory Limit:

Description

坑校准备鼓励学生参加学习小组。
共有个学生，个学习小组，每个学生有一定的喜好，只愿意参加其中的一些学习小组，但是校领导为学生考虑，规定一个学生最多参加个学习小组。财务处的大叔就没那么好了，他想尽量多收钱，因为每个学生参加学习小组都要交一定的手续费，不同的学习小组有不同的手续费。然而，事与愿违，校领导又决定对学习小组组织者进行奖励，若有个学生参加第i个学习小组，那么给这个学习小组组织者奖励元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱（若为负数，则输出负数）（）。

Input

输入有若干行，第一行有三个用空格隔开的正整数。接下来的一行有个正整数，表示每个。第三行有个正整数，表示参加每个学习小组需要交的手续费。再接下来有一个行列的矩阵，表若第行列的数字是，则表示第个学生愿意参加第个学习小组，若为，则为不愿意。

Output

输出只有一个整数，为最小的支出。

Problem

【HNOI2001】软件开发

Time Limit:
Memory Limit:

Description

某软件公司正在规划一项天的软件开发计划，根据开发计划第天需要个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，种方式的消毒需要天时间，种方式的消毒需要天（），种消毒方式的费用为每块毛巾, 种消毒方式的费用为每块毛巾，而买一块新毛巾的费用为（新毛巾是已消毒的，当天可以使用）；而且。公司经理正在规划在这天中，每天买多少块新毛巾、每天送多少块毛巾进行种消毒和每天送多少块毛巾进行种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行种消毒和多少毛巾进行种消毒，使公司在这项天的软件开发中，提供毛巾服务的总费用最低。

Input

第行为. 第行为. （注：）

Output

最少费用