codeforces B. Mishka and trip

淩亂°似流年 2022-07-18 18:27 81阅读 0赞

B. Mishka and trip

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Mishka is a great traveller and she visited many countries. After thinking about where to travel this time, she chose XXX — beautiful, but little-known northern country.

Here are some interesting facts about XXX:

1.  XXX consists of *n* cities, *k* of whose (just imagine!) are capital cities.
2.  All of cities in the country are beautiful, but each is beautiful in its own way. Beauty value of *i*\-th city equals to *c**i*.
3.  All the cities are consecutively connected by the roads, including 1\-st and *n*\-th city, forming a cyclic route 1 — 2 — ... — *n* — 1. Formally, for every 1 ≤ *i* < *n* there is a road between *i*\-th and *i* + 1\-th city, and another one between 1\-st and *n*\-th city.
4.  Each capital city is connected with each other city directly by the roads. Formally, if city *x* is a capital city, then for every1 ≤ *i* ≤ *n*,  *i* ≠ *x*, there is a road between cities *x* and *i*.
5.  There is **at most one** road between any two cities.
6.  Price of passing a road directly depends on beauty values of cities it connects. Thus if there is a road between cities *i* and *j*, price of passing it equals *c**i*·*c**j*.

Mishka started to gather her things for a trip, but didn't still decide which route to follow and thus she asked you to help her determine summary price of passing **each of the roads** in XXX. Formally, for every pair of cities *a* and *b* (*a* < *b*), such that there is a road between*a* and *b* you are to find sum of products *c**a*·*c**b*. Will you help her?

Input

The first line of the input contains two integers *n* and *k* (3 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ *n*) — the number of cities in XXX and the number of capital cities among them.

The second line of the input contains *n* integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ 10 000) — beauty values of the cities.

The third line of the input contains *k* distinct integers *id*1, *id*2, ..., *id**k* (1 ≤ *id**i* ≤ *n*) — indices of capital cities. Indices are given in ascending order.

Output

Print the only integer — summary price of passing each of the roads in XXX.

Examples

input

4 1
    2 3 1 2
    3

output

input

5 2
    3 5 2 2 4
    1 4

output

Note

This image describes first sample case:

![171ddc86762c931ed2d5f9f3b8ebed6d12503783.png][]

It is easy to see that summary price is equal to 17.

This image describes second sample case:

![0ff4a66cf522731c8f69ee0a5a59fa3dfb71de68.png][]

It is easy to see that summary price is equal to 71.

题意：有n个城市连成一个环，m个主要城市，每两个城市之间最多有一条路，每个主要城市都有通向其他所有城市的一条路，每条道路的权值是两端城市的值的乘积，求总的路线权值是多少。

分析：这种题都不会做了。。。比赛的时候竟然没有做出来。假设当前的主要城市是i，那么这个城市有通向其他所有城市的道路，算一下就是c\[i\]\*(sum-c\[i\])，遍历所有的主要城市统计答案就行了，但是每一个主要城市的道路都被统计了两次，我们需要在统计的过程中不断把sum-c\[i\]，i是当前主要城市的id，最后主要把相邻的非主要城市的道路权值加上就行了。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    ll a[N];
    bool vis[N];
    int cap[N];
    
    
    int main()
    {
        int n=in(),m=in();
        ll sum=0;
        for(int i=0;i<n;i++){
            a[i] = in();
            sum += a[i];
        }
        for(int i=0;i<m;i++){
            cap[i]=in()-1;
            vis[cap[i]]=1;
        }
        ll ans=0;
        for(int i=0;i<n-1;i++){
            if(!vis[i] && !vis[i+1]) ans += a[i]*a[i+1];
        }
        if(!vis[0] && !vis[n-1]) ans += a[0]*a[n-1];
        for(int i=0;i<m;i++)
        {
            ans += (sum-a[cap[i]])*a[cap[i]];
            sum -= a[cap[i]];
        }
        cout<<ans<<endl;
        return 0;
    }

[171ddc86762c931ed2d5f9f3b8ebed6d12503783.png]: /images/20220718/67d08470fd8441bb85b4fe60d050bc32.png
[0ff4a66cf522731c8f69ee0a5a59fa3dfb71de68.png]: /images/20220718/58546e01e6e74a64994fb1917d9ffd63.png