You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

一维vector

  除非迫不得已，否则我们在教程题目中不讨论 C 语言的情形，专注于 C++ 的特性。

  当我们需要存储大量数据时，例如 10000 个，声明这么多变量显然是不现实的，因此，对于同一种类型的数据，我们需要用一些数据结构进行存储。

  我们从最常用的数组开始讨论，在 C++ 中我们应尽量采用 vector，既可以当作静态数组、也可以当作动态数组使用。（为节约时间，后续需要的引入头文件一般就是类型名字，如 #include <vector>，不再赘述）

  首先声明一些一维的 vector

vector<int> vec;
vector<string> strings;

  类型为 vector<int>，说明这是一个存放 int 类型的 vector，变量名为 vec。第二行同理，是一个存放 string 类型的 vector

push_back

  如果需要在 尾部 添加元素，使用 push_back(x)，其中 x 是新增的元素

int x = 5;
vec.push_back(x);
vec.push_back(3);

  这样，原本为空的数组，就有了两个值：[5, 3]

  数组可以直接由下标访问，例如

cout << vec[1] << " " << vec[0] << endl;

  输出的结果是 3 5（注意，通常下标都是从0开始）

insert

  如果要在某个位置插入元素，需要使用 insert(pos, elem)，可能你需要在后面的 STL 章节才能完全理解，这里只需要了解使用方法即可。

vector<int> nums = {1, 2};

nums.insert(nums.begin() + 1, 3);

  在位置 1 插入 3，执行后 nums[1] 变为 3，在原来位置 1 及在其之后的元素均往后挪一个位置。此时 nums 变为 1, 3, 2

size

  size() 函数可以获取这个 vector 当前的大小，例如

vector<double> nums;
nums.push_back(1.0);
cout << nums.size() << " ";

nums.push_back(5.0);
nums.push_back(2.0);
cout << nums.size() << " ";

  可以得到 1 3

  当然，这样的动态添加适用于数据量未知的情况，实际上是比较慢的，因此，在数据量已知，或者数据量范围已知的情况下，我们可以直接申请一个指定大小的数组，这样效率较高，如

const int MAXN = 100000 + 5  // 可简单写成1e5 + 5
vector<int> vec(MAXN);

  需要注意的是，在初始化时指定大小，内容是常量，如用 const 定义的常量 MAXN，或者直接写 100005。 你可以尝试定义一个变量如 int n = 5，那么此时用 vec(n) 声明时，相当于直接声明大小为 5，而对 n 进行修改，不影响 vec 的大小。

  那么，我们是否有办法在运行过程中快速改变 vector 的大小呢？使用 resize(new_size) 即可

int n;
cin >> n;
vec.resize(n);

  上述代码就将已经定义好的 vector，改变大小为从控制台输入的 n

简化遍历方法

  与 C 语言最接近的方法，我们可以用下标来遍历 vector，如下所示

vector<int> nums;
...
for (int i = 0; i < nums.size(); ++i) {
   // do something...
}

  除了用下标遍历之外，如果我们想要遍历 vector 中所有元素，还可以用下面的形式：

vector<int> nums;
...
for (int x : nums) {
    // do something...
}

  如果再用之后介绍的 auto，则会更加方便，可以自动推导元素的类型，不论 vector 元素是什么类型，都只需要一个 auto 即可。

vector<double> nums;
...
for (auto x : nums) {
    // do something...
}

二维vector

  在 vector 中存放的类型几乎是任意的，除了常用类型如 vector<int>, vector<double>, vector<string> 等之外，我们也可以在 vector 中存放 vector，例如

vector<vector<int>> nums;

  注意到 nums 这个 vector，每个位置所存放的元素的类型是 vector<int>。换言之，用 nums[i] 取出的内容，是一个 vector<int>，例如（我们可以通过如下所示的操作，用花括号初始化 vector 的内容）

vector<int> vec1 = {1, 2, 3, 4, 5};
vector<int> vec2 = {6, 7, 8, 9, 10, 11};
nums.push_back(vec1);
nums.push_back(vec2);

特别注意：将 vec1 和 vec2 放进 nums 后，vec1、vec2 与 nums 无关，即改变 vec1 内的值，并不能改变 nums 内的值

  这样一来，原本为空的 nums 就有了两个 vector<int>，我们可以先用 nums[i] 取出第 i 个 vector<int>，再对其进行操作，例如：

cout << nums[1].size() << " " << nums[0].size() << endl;

  我们分别取出第 1 个和第 0 个 vector，并输出它们的大小，结果是 6 5

  既然我们取出的内容是一个 vector<int>，那么我们就可以对它进行一维 vector的所有操作，如

for (int i = 0; i < 3; i++) {
    cout << nums[1][i] << " ";
}

  用 nums[1] 取出第 1 个 vector<int>，即可通过下标访问其中的元素，例如此处访问下标为 0-2 的 3 个元素，输出结果是 6 7 8

快速初始化

  对于 nums 这样的二维 vector，我们在大小已知时，动态添加一维 vector 依然耗时，例如对于给定的 n*m 矩阵，需要一种初始化方法快速地构建一个二维 vector。

  一维 vector 初始化时，我们只给定了它的大小，事实上此时初值默认为 0，我们也可以在初始化时同时指定初值，例如

vector<int> vec(MAXN, 1);

  这样就使得 vec 里的值全部为 1。自然，我们也可以用同样的方法来初始化一个二维的 vector，例如

vector<vector<int>> nums(M, vector<int>(N));

  可以看到，nums 的大小为 M，含有 M 个大小为 N 的一维 vector。

  总之，我们不要把二维 vector 当作传统的二维数组来看待，只需要看成一个 vector，只不过这个 vector 里面所装的元素是一个个 vector 而已。因此只要是 vector 的操作，我们都可以运用在 nums 上。

Description

  对于给定的矩阵 $A_{m\times n}$，分别求出矩阵的 1 范数 $||A||_1$ 与矩阵的无穷范数 $||A||_{\infty}$

Format

Input

  第一行为两个整数 $m, n \space(1 \leq n, m \leq 500)$，表示矩阵的行数与列数

  接下来 $m$ 行，每行有 $n$ 个 浮点数，表示矩阵的值 $a_{ij} \space (|a_{ij}| \leq 10^5)$

Output

  两个数，分别表示矩阵的 1 范数和无穷范数

Samples

2 2
1.5 2.7
3.4 9.8

12.5 13.2

3 4
2 3 -5 -7
4 6 8 -4
6 -11 -3 16

27 36