← 返回题目列表

AtCoder · KeioPC2025_n

N. 时间表总和

中文机器翻译题面 查看原题

配点 : 101 点

問題文

N×N 我有一个正方形网格。从上面 i 行,从左起 j 选择列中的方块。 (i,j)(1≤i,j≤N) 。

每个方格都有一个整数 1 上面写道,(i,j) 有 写入 i×j 。 从

(1,1) 开始并重复移动到右侧或底部的方块, 前往 (N,N) 的路线好路线 它被称为。此时,好路线的分数被定义为“所经过的方格上写的数字的总和”。

一条好路线的最大可能得分是 M 。M 找到未显示为良好路线分数的最大整数。

制約

  • 2 \le N \le 1000
  • 所有输入均为整数 如果正确答案是满足

部分点

针对此问题设置了部分分数。 如果正确答案是满足

  • N \le 30 的数据集 1 点。 如果正确答案是满足

入力

输入将以以下格式从标准输入给出。

N

出力

打印答案。 每个加油站的


入力例 1

3

出力例 1

20

例如,考虑上图中所示的路线。

  • 红色路线的分数是 1 + 2 + 3 + 6 + 9 = 21 。
  • 蓝色路线的得分是 1 + 2 + 4 + 6 + 9 = 22 。

还有其他可能的路线,但是N = 3 如果是 M = 22 。并且,M 不作为路线分数出现的最大整数是 20 。


入力例 2

6

出力例 2

152

入力例 3

9

出力例 3

476