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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

int bitFactor(unsigned long long int bit) {
  int i=0;
  unsigned long long int p;

  if (bit <= 1) return (int)bit;
  do {
    p = pow(2, i++);
  } while(p < bit);

  p = pow(2, i-2);

  return 1 + bitFactor(bit % p);
}

bool reassignJumps(unsigned long long int *&jumps,  unsigned long long int limit, int size) {
  for (int i=0; i<size; i++) {
    if (jumps[i]+size-i-1 >= limit) {
      if (i == 0) return false;
      jumps[i-1]++;
      jumps[i] = jumps[i-1]+1;
      for (int j=i+1; j<size; j++) {
        jumps[j] = jumps[j-1]+1;
      }
      return true;
    }
  }
  
  jumps[size-1]++;
  return true;
}

int main(int argc, char const *argv[]) {
  bool finish = false;
  int numberOfSeconds;
  unsigned long long int bitLimit, i, iterations=0, *jumps;
  long long int *rates, sum, sumTmp;

  if (!scanf("%d %llu", &numberOfSeconds, &bitLimit)) return 1;
  rates = (long long int *) malloc(numberOfSeconds * sizeof(long long int));
  jumps = (unsigned long long int *) malloc(numberOfSeconds * sizeof(unsigned long long int));
  
  for (i=0; i<numberOfSeconds; i++) {
    if (!scanf("%lli", &rates[i])) return 1;
    jumps[i] = i==0 ? 0 : jumps[i-1]+1;
  }
  
  while (true) {
    sumTmp = 0;
    for (int i=0; i<numberOfSeconds; i++) {
      sumTmp += rates[i]*bitFactor(jumps[i]);
    }
    if (iterations == 0 || sumTmp > sum) sum = sumTmp;

    iterations++;
    if (!reassignJumps(jumps, bitLimit, numberOfSeconds)) break;
  }

  printf("%lli %llu", sum, iterations);
  free(rates);
  free(jumps);
  
  return 0;
}