eolymp
bolt
Try our new interface for solving problems
Məsələlər

Потенциал строки

Потенциал строки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Задана строка s, состоящая из k первых маленьких букв латинского алфавита. Как и в предыдущей задаче, расстоянием между двумя символами этой строки s_i, s_j будем считать разницу между их позициями, то есть |j−i|. Определим потенциал этой строки следующим образом. Пусть известна функция f(c_1,c_2), которая каждой паре букв ставит в соответствие некоторый вес. Эта функция является симметричной относительно своих аргументов, то есть f(c_1,c_2) = f(c_2,c_1). Потенциалом между парой символов s_i и s_j строки s назовем произведение их весовой функции на расстояние между ними. Потенциал строки будет тогда вычисляться как суммарный потенциал между всеми парами символов.

Напишите программу, определяющую потенциал заданной строки s.

Giriş verilənləri

В первой строке входного файла записано целое число k (1k26), количество первых букв латинского алфавита, которые могут быть в строке. Во второй строке задается строка s. Ее длина не превышает 10^6. В последующих k строках задается весовая функция, i-ая из них содержит i чисел, j-ое из которых означает величину веса для i-ой и j-ой в порядке алфавита латинской буквы. Все веса не превосходят 10^6 по абсолютной величине.

Çıxış verilənləri

В выходной файл необходимо вывести одно число – потенциал строки s.

Nümunə

Giriş verilənləri #1
3
abcacba
1
0 1
1 0 1
Çıxış verilənləri #1
32
Mənbə International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011