3881: 声东击西(挖土机 CSP-J 模拟赛 ~ 第八场)

内存限制:256 MB 时间限制:3.000 S
评测方式:文本比较 命题人:cyhpl
提交:3 解决:1

题目描述

33DAI 和 Kitten 正在玩一款游戏。游戏中有  个城市(>1),从左到右编号从 1,编号为  的城市有  的资源。

Kitten 可以任选一个城市开始实行声东击西战略,假设她选择城市 。那么 33DAI 就会警觉并前往城市 。这需要花费 33DAI  分钟的时间。33DAI 到达后就会封锁城市  使得不能从 1 走到 ,也不能从 +1 走到 。如果此时 Kitten 就在城市 ,那么 Kitten 就会直接输掉游戏。

Kitten 每分钟可以选择待在原地或者走到左边或者右边的城市(即从城市  走到城市 +1 或 1)。

请你帮 Kitten 决定起始城市及每分钟的移动策略,来不输掉游戏,并最大化她到过的城市资源之和。

输入

第一行为一个数 

第二行为  个整数 1

输出

一个整数,即她到过的城市资源之和的最大值。

样例输入 复制

2
-5 2

样例输出 复制

-3

提示


数据规模与约定

对于 100% 的数据,2106109109

  • 子任务 1(10 分):保证 =2
  • 子任务 2(20 分):保证 >=0
  • 子任务 3(30 分):保证 =100
  • 子任务 4(40 分):没有特殊限制。

来源/分类