1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <vector>
#include <algorithm>

struct Client
{
    Client(const long long int count, const long long int time) : m_count(count), m_time(time) {}
    const long long int m_count;
    const long long int m_time;
};

void readClients(int n, std::vector<Client>& clients)
{
    long long int time, lastTime = -1;
    int tmpClientsCount = 0;
    for (int i=0; i<n; ++i)
    {
        scanf("%lld", &time);
        if (time == lastTime)
        {
            tmpClientsCount++;
        }
        else
        {
            if (lastTime != -1)
            {
                clients.emplace_back(tmpClientsCount, lastTime);
            }
            lastTime = time;
            tmpClientsCount = 1;
        }
    }
    clients.emplace_back(tmpClientsCount, lastTime);
}

long long int count(const long long int bakeTime, const std::vector<Client>& clients)
{
    long long int endTime = 0;
    long long int waitTime = 0;
    for (const auto client : clients)
    {
        const long long int reallyStartTime = std::max(endTime, client.m_time - bakeTime);
        const long long int beforeStartWaitTime = reallyStartTime + bakeTime - client.m_time;
        const long long int afterStartWaitTime = ((client.m_count - 1) * client.m_count / 2) * bakeTime;
        waitTime += beforeStartWaitTime * client.m_count + afterStartWaitTime;;
        endTime = reallyStartTime + bakeTime * client.m_count;
    }
    return waitTime;
}

int main(int, char **)
{
    int n, m, bakeTime;

    std::vector<Client> clients;
    scanf("%d %d", &n, &m);
    readClients(n, clients);

    for (int i=0; i<m; ++i)
    {
        scanf("%d", &bakeTime);
        printf("%lld\n", count(bakeTime, clients));
    }
    return 0;
}