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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <algorithm>
#include <vector>

int main( ) {
	//printf("Hello\n");
	int n; // liczba klientów
    int	m; // liczba piekarników
	scanf("%d %d", &n, &m);
	int i,j;
	unsigned long long t[200000] = {}; // czasy
	unsigned long long diffT[200000] = {}; // różnice między timestampami
	int p[200000] = {}; // piekarniki - czasy pieczenia
	unsigned long long lastP[200000] = {}; // piekarniki - czasy pieczenia
	std::vector<int> notAnalyzedIdx = std::vector<int>(); 
	std::vector<int> newNotAnalyzedIdx = std::vector<int>();
	std::vector<int> tmp;
	
	for(i = 0 ; i < 200000; i++) {
		diffT[i] = 0;
		p[i] = 0;
		lastP[i] = 0;
		t[i] = 0;
	}
	
	unsigned long long partialDiffSum = 0;
	
	notAnalyzedIdx.resize(n);
	newNotAnalyzedIdx.reserve(n);
    unsigned long long prev = 0;
	unsigned long long arithmeticSum = ((1+n)*n)/2;
	//printf("Arithmetic sum %lld\n", arithmeticSum);
	for(i = 0 ; i < n; i++) {
		unsigned long long x = 0;
		scanf("%lld", &x);
		t[i] = x;
		diffT[i] = x - prev;
		prev = x;
		notAnalyzedIdx[i] = i;
		//printf("Some data %lld %d\n", diffT[i], notAnalyzedIdx[i]);
	}
	for(i = 0 ; i < m; i++) {
		int x = 0;
		scanf("%d", &x);
		p[i] = x;
		//printf("Piekarnik %d", p[i]);
	}
	//std::sort(p, p+m);
	
	for(i = 0 ; i < m; i++) {
		int pTime = p[i];
		unsigned long long sum = 0;
		for(j = 0 ; j < n; j++) {
			lastP[i] = std::max(lastP[i] + pTime, t[j]);
			sum = sum + lastP[i] - t[j];
			//printf("Piekarnik %d %lld %lld %lld", pTime, lastP[i], t[j], sum);
		}
		printf("%lld\n", sum);
		/*newNotAnalyzedIdx.clear();
		int pTime = p[i];
		printf("ptime %d\n", pTime);
		for(j = 0 ; j < notAnalyzedIdx.size(); j++) {
			int idx = notAnalyzedIdx[j];
			printf("idx %d\n", idx);
			unsigned long long timeDiff = diffT[idx];
			if (timeDiff > pTime) {
				newNotAnalyzedIdx.push_back(idx);
			} else {
				int numberOfAffected = n - idx;
				partialDiffSum += numberOfAffected*timeDiff;
			}
		}
		unsigned long long affectedArithmeticSum = arithmeticSum;
		for (j = 0; j < newNotAnalyzedIdx.size(); j++) {
			affectedArithmeticSum = affectedArithmeticSum - newNotAnalyzedIdx[j];
		}
		unsigned long long result = affectedArithmeticSum * pTime - partialDiffSum;
		printf("partial %lld\n", partialDiffSum);
		tmp = notAnalyzedIdx;
		notAnalyzedIdx = newNotAnalyzedIdx;
		newNotAnalyzedIdx = tmp;
		printf("out %lld\n", result);*/
	}

	return 0;
}