Решение математической задачи «Мишка и путешествие» - C#

Формулировка задачи:

Маленькая Мишка — большая путешественница. В каких только странах она не побывала! После долгих раздумий о том, куда бы поехать в этом году, выбор её пал на XXX — прекрасную, но малоизвестную северную страну. Вот несколько интересных фактов об этой стране: В состав XXX входят n городов, k из которых (только представьте себе!) являются столицами. Все города этой страны красивы, но по-разному. Красота i-го города описывается величиной ci. Все города последовательно соединены дорогами, включая 1-й и n-й город, образуя замкнутый маршрут 1 — 2 — ... — n — 1. Формально, для каждого 1 ≤ i < n существует дорога между городами i и i + 1, и еще одна между городами 1 и n. Каждый город-столица напрямую соединен дорогами со всеми остальными городами. Формально, если город x — столица, то для каждого 1 ≤ i ≤ n, i ≠ x, существует дорога между городами x и i. Между любыми двумя городами существует не более одной дороги. Стоимость проезда между городами напрямую зависит от показателей их красоты. Так, если между городами i и j существует дорога, то стоимость проезда по ней равна c_i·c_j. Мишка уже начала собираться в путешествие, но ещё не определилась со своим маршрутом, а потому попросила вас помочь ей оценить суммарную стоимость проезда по всем дорогам XXX. Формально, по всем различным парам городов a и b (a < b), таких, что a и b соединены дорогой, требуется посчитать сумму произведений c_a·c_b. Поможете ей?

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

В первой строке входных данных содержатся числа n и k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — количество городов в XXX и количество столиц среди них соответственно. Во второй строке содержится n целых чисел c₁, c₂, ..., c_n (1 ≤ ci ≤ 10 000) — показатели красоты каждого из городов. В третьей строке содержится k различных целых чисел id₁, id₂, ... id_k (1 ≤ id_i ≤ n) — номера городов, являющихся столицами. Номера городов заданы в порядке возрастания.

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

Выведите единственное целое число — суммарную стоимость проезда по всем существующим дорогам в XXX.

Решение задачи: «Решение математической задачи «Мишка и путешествие»»

textual
                            Листинг программы 
                        
 
                            
                        
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        //InputReader in = new InputReader(new FileInputStream("input.txt"));
        Task solver = new Task();
        solver.solve(in);
    }
}
 
 
class Task {
    public static final int MAXN = 100003;
 
    public void solve(InputReader in) throws IOException {
        int n = in.readInt();
        int k = in.readInt();
        long[] beauty = new long[MAXN];
        long beautySum = 0;
        for (int i = 0; i < n; ++i) {
            beauty[i] = in.readLong();
            beautySum += beauty[i];
        }
        long cost = 0;
        Set<Integer> caps = new HashSet<>();
        while (k-- > 0) {
            int cap = in.readInt() - 1;
            cost += beauty[cap] * (beautySum - beauty[cap]);
            beautySum -= beauty[cap];
            caps.add(cap);
 
        }
        for (int i = 0, j = 1; i < n; ++i, j = (j + 1) % n) {
            if (!caps.contains(i) && !caps.contains(j)) {
                cost += beauty[i] * beauty[j];
            }
        }
        System.out.println(cost);
 
    }
}
 
 
class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;
 
 
    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }
 
 
    public String readLine() {
        try {
            return reader.readLine();
        }
        catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
 
 
    public String readToken() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(readLine());
        }
        return tokenizer.nextToken();
    }
 
 
    public int readInt() {
        return Integer.parseInt(readToken());
    }
 
 
    public long readLong() {
        return Long.parseLong(readToken());
    }
 
 
    public double readDouble() {
        return Double.parseDouble(readToken());
    }
}