← 返回题目列表

AtCoder · scpc2026_div3_d

D. 寿司回转台寿司店

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

表示言語

/ /

分数: 100 点

问题陈述

utilForever 参观了 Sushisushi 传送带寿司店。其输送带共有 N 可以放置寿司的位置。最初, K_i 寿司堆放在 i-第一个位置,并吃 j- 从顶部开始的第一个寿司 i第一个位置让人满意 X_{i,j}. X_{i,j} 可能为负。

从今天的午餐开始,utilForever将吃 T 天。每天午餐时,utilForever 最多可以吃一个寿司,即该位置寿司中最顶级的寿司 1。传送带移动经过 每晚 1 位置。位置好的寿司 i+1 移动到位置 i,以及位于位置的寿司 1 移动到位置 N.

找出 utilForever 可以获得的最大可能总满意度。

约束

  • 1 \leq N,T \leq 10^6
  • 0 \leq K_i \leq 10^6
  • \sum_{i=1}^N K_i \leq 10^6
  • -100 \leq X_{i,j} \leq 100
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N T
K_1 X_{1,1} X_{1,2} \dots X_{1,K_1}
K_2 X_{2,1} X_{2,2} \dots X_{2,K_2}
\vdots
K_N X_{N,1} X_{N,2} \dots X_{N,K_N}

输出

输出 utilForever 可以获得的最大可能总满意度。


示例输入 1

4 10
5 31 4 -15 9 26
3 53 -5 -89
3 -79 -32 -38
0

示例输出 1

88

表示言語

/ /

점수 : 100 점

문제

utilForever는스시스시회전초밥집에갔다。 스시스시 회전초밥집의 회전초밥 레일에는 초밥을 놓을 수 있는 칸 Been N개 있다. 처음에 i번째 칸에는 초밥이 K_i개 쌓여 있으며, 그중 i번째 칸의 위에서 j번째 초밥을 먹으면 만족감을 X_{i,j}만큼 얻을 수 있다. X_{i,j}가 음수일 수도 있다.

utilForever는 오늘 점심부터 T일 동안 식사를 하려 한다. 매일 점심 utilForever는 1번 칸에 있는 초밥 중 가장 위에 있는 초밥을 최대 하나 먹을 수 있다. 회전초밥 레일은 매일 밤 1칸씩 이동한다. i+1번 칸에 있던 초밥은 i번 칸으로 이동하고 1번 칸에 있던 초밥은 N번 칸으로 이동한다.

utilForever 已修复并已修复。

제한

  • 1 \leq N,T \leq 10^6
  • 0 \leq K_i \leq 10^6
  • \sum_{i=1}^N K_i \leq 10^6
  • -100 \leq X_{i,j} \leq 100
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N T
K_1 X_{1,1} X_{1,2} \dots X_{1,K_1}
K_2 X_{2,1} X_{2,2} \dots X_{2,K_2}
\vdots
K_N X_{N,1} X_{N,2} \dots X_{N,K_N}

출력

utilForever 已修复并已修复。


입력 예 1

4 10
5 31 4 -15 9 26
3 53 -5 -89
3 -79 -32 -38
0

출력 예 1

88