e-olymp 610. Древняя рукопись

Задача

В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках упоминается, что их точно было не менее трех. С течением времени у них появились дети и разбрелись они по миру, причем как и их родители, каждый построил свой город. Опять же с течением времени количество родственников начало стремительно возрастать и решили они между некоторыми городами построить дороги, а некоторые из них, уже до этого успели построить и объездные дороги вокруг своего города. В рукописях упоминается, что количество городов в той стране не превышало $8000$. Кроме того, в тех же рукописях содержались схематические карты, которые показывали наличие дорог между городами, или объездной дороги вокруг города. Карты имели вид квадратных матриц, в которых цифра $1$ указывала на наличие дороги между городами, или вокруг города, или $0$ в случае отсутствия таковой.

Изучите древние рукописи и дайте ответ на вопрос: а сколько же дорог было построено между городами?

Входные данные

В первой строке задано количество городов $n$, а в последующих $n$ строках через пробел задано по $n$ чисел, которые указывают на наличие или отсутствие соответствующей дороги.

Выходные данные

Количество построенных между городами дорог.

Тесты

Входные данные	Выходные данные
5 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1	7
4 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0	3
3 1 1 0 1 0 1 0 1 0	2
3 0 1 1 1 0 1 1 1 0	3
3 1 0 0 0 1 0 0 0 1	0

Код программы

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int n, k = 0;
    cin >> n;     cin.ignore(); //считываем n и игнорируем символ перевода строки
    const int N = 2 * n + 1;
    char c[N];
    for(int i = 0; i < n; i++) {
        fgets(c, N, stdin); //считываем строку
        for(int j = 0; j < i; j++) 
            k = k + c[j << 1] - 48; //переводим символ из ascii кода в число
    }
    cout << k;

    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main() {

int n, k = 0;

cin >> n; cin.ignore(); //считываем n и игнорируем символ перевода строки

const int N = 2 * n + 1;

char c[N];

for(int i = 0; i < n; i++) {

fgets(c, N, stdin); //считываем строку

for(int j = 0; j < i; j++)

k = k + c[j << 1] - 48; //переводим символ из ascii кода в число

}

cout << k;

return 0;

}

Решение задачи

Задача не сложная – посчитать количество ребер в графе, заданном матрицей смежности.

Сложность задачи состоит в ограничениях по времени – не более одной секунды (ощутимо при больших значенях $n$, так как $3 ≤ n ≤ 8000$). Поэтому приходится быстро вводить данные в больших количествах. Для этого используем символьный массив и любую функцию, которая читает целую строку чисел (в моем случае – fgets()), которая читает строку, пока не встретит символ перевода строки – '\n'.

Далее по одному переводим символы в числа и суммируем их в переменной k, после чего выводим.