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 #include #include 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 notAnalyzedIdx = std::vector(); std::vector newNotAnalyzedIdx = std::vector(); std::vector 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; }