CodeForces 831C Jury Marks [set]

Polycarp watched TV-show where k jury members one by one rated a participant by adding him a certain number of points (may be negative, i. e. points were subtracted). Initially the participant had some score, and each the marks were one by one added to his score. It is known that the i-th jury member gave a_i points.

Polycarp does not remember how many points the participant had before this k marks were given, but he remembers that among the scores announced after each of the k judges rated the participant there were n (n ≤ k) values b₁, b₂, ..., b_n (it is guaranteed that all values b_j are distinct). It is possible that Polycarp remembers not all of the scores announced, i. e. n < k. Note that the initial score wasn't announced.

Your task is to determine the number of options for the score the participant could have before the judges rated the participant.

Input

The first line contains two integers k and n (1 ≤ n ≤ k ≤ 2 000) — the number of jury members and the number of scores Polycarp remembers.

The second line contains k integers a₁, a₂, ..., a_k ( - 2 000 ≤ a_i ≤ 2 000) — jury's marks in chronological order.

The third line contains n distinct integers b₁, b₂, ..., b_n ( - 4 000 000 ≤ b_j ≤ 4 000 000) — the values of points Polycarp remembers. Note that these values are not necessarily given in chronological order.

Output

Print the number of options for the score the participant could have before the judges rated the participant. If Polycarp messes something up and there is no options, print "0" (without quotes).

Examples
input
4 1 
-5 5 0 20 
10
output
3
input
2 2 
-2000 -2000 
3998000 4000000
output
1

Note

The answer for the first example is 3 because initially the participant could have - 10, 10 or 15 points.

In the second example there is only one correct initial score equaling to 4 002 000.

题目大意：Polycarp看电视选秀，k个评委给一个参赛者打分，每个评委打了ai分。评委每给一次分，就会与参赛者的初始分相加得到一个结果，即bj。但是Polycarp只记得其中的一些结果，问你参赛者的初始分有多少种可能。（ai是按顺序给出，而bj不一定）

Note中也给出了相关说明，4个评委给出了-5,5,0,20的分数，Polycarp只记得10一个结果。10有可能是给出-5之后的结果，所以初始分为15。也有可能是在给出-5和5之后的结果，所以初始分是10，以此类推。

大致思路：不难看出，评委给分的前缀和中有多少不同的数即为不同初始分（答案）的最大值，再枚举可能的初始分，判断是否有对应的结果。利用STL中的set的insert()可以省去前缀和去重的步骤，count()可以用来计数。详见代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
#define maxn 2005
set<int> s;
set<int>::iterator its;//迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型
int main()
{
    int a[maxn],b[maxn],sum[maxn];
    int x,,start,i,k,n;
    while(scanf("%d%d",&k,&n)==2)
    {
        memset(sum,0,sizeof(sum));//主要是sum[0]=0
        s.clear();
        for(i=1;i<=k;i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];//计算前缀和
            s.insert(sum[i]);//把前缀和记录到set中
        }
        for(i=0;i<n;i++)
            cin>>b[i];
        int ans=s.size();//这时的ans是所求可能情况的最大值
        for(its=s.begin();its!=s.end();its++)//遍历set，返回每一个前缀和
        {
            x=*its;//用x记录当前set中的key值
            start=b[0]-x;//初始值=某个结果-某个前缀和   即枚举初始值
            for(i=0;i<n;i++)
            {
                if(!s.count(b[i]-start))//判断是否有对应的前缀和
                {
                    ans--;
                    break;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

CodeForces 831C Jury Marks [set]

推荐阅读