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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 #include #include #include #include typedef unsigned long long big; typedef unsigned int var; //using namespace std; std::vector vec; std::vector diffs; void wczytaj(var n) { big x = 0; for (size_t i=0;i < n;++i) { scanf("%lld", &x); vec[i]=x; } } big naLewo(var i) { return diffs[i-1] + (vec[i] - vec[i-1])*(i); } void pass(var /*n*/) { std::sort(vec.begin(), vec.end()); size_t nax = vec.size(); vec[0] = vec[0]; big last = vec[0]; for (size_t i=1;i < nax ;++i) { big tmp = vec[i]; vec[i] -= last; last = tmp; } std::sort(vec.begin(), vec.end()); diffs.resize(nax); diffs[0] = 0; for (size_t i=1;i < nax ;++i) { diffs[i] = naLewo(i); } } big policzKoszt(var d) { big cost = 0; auto right = std::lower_bound(vec.begin(), vec.end(), d); if (right == vec.end()) { big top =* (right - 1); var index = right - vec.begin() - 1; cost = (d - top) * (index+1) + diffs[index]; } else if (right == (vec.end() - 1)) { // last big top =*right; var index = right - vec.begin(); cost = (d - top) * index + diffs[index]; } else { //equal or lower big top =*right; var index = right - vec.begin(); cost = (d - top) * index + diffs[index]; } return cost; } void wypiszWyniki(var m) { for (size_t i=0;i < m;++i) { var d; scanf("%d", &d); big cost = policzKoszt(d); printf("%lld\n", cost); } } #ifndef UT int main() { var n = 0; var m = 0; #ifndef T1 scanf("%d %d", &n, &m); #endif vec.resize(n); #ifndef T1 wczytaj(n); #endif pass(n); #ifndef T1 wypiszWyniki(m); #endif return 0; } #endif