题目详情题解（0）讨论（0）提交记录（0）

AT_relay2_h.Akashic Records

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

考虑一个由无限多个项组成的数列 a1,a2,…a_1, a_2, \ldots。最初，所有项的值均为 00，在这一状态下，持续进行 QQ 次操作，第 ii 次操作（1≤i≤Q1 \leq i \leq Q）如下所示：

  • 对于所有正整数 jj，将 aj×mia_{j \times m_i} 的值加上 xix_i。

请在这 QQ 次操作全部结束后，求出数列中最大的项的值。

输入格式

输入通过标准输入按以下格式给出：

QQ
m1 x1m_1\ x_1
⋮\vdots
mQ xQm_Q\ x_Q

输出格式

请输出经过 QQ 次操作后数列中最大项的值。

输入输出样例

  • 输入#1

    3
2 10
3 -20
6 15

    输出#1

    10

  • 输入#2

    3
10 -3
50 4
100 -5

    输出#2

    1

  • 输入#3

    5
56 114834
72 -149861
100 190757
192 -132693
240 133108

    输出#3

    438699

说明/提示

限制条件

  • 1≤Q≤2991 \leq Q \leq 299
  • 2≤mi≤3002 \leq m_i \leq 300
  • −106≤xi≤106-10^6 \leq x_i \leq 10^6
  • mim_i 互不相同
  • 所有输入均为整数

样例解释 1

数列各项 a1,a2,…a_1, a_2, \ldots 的值变化如下：

  • 操作前：0,0,0,0,0,0,…0, 0, 0, 0, 0, 0, \ldots
  • 第 1 次操作后：0,10,0,10,0,10,…0, 10, 0, 10, 0, 10, \ldots
  • 第 2 次操作后：0,10,−20,10,0,−10,…0, 10, -20, 10, 0, -10, \ldots
  • 第 3 次操作后：0,10,−20,10,0,5,…0, 10, -20, 10, 0, 5, \ldots

所有操作完成后，最大的项的值为 1010。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页