Tikut

#include <bits/stdc++.h>
 
using namespace std;
 
int recursiveCutting(vector<int>& a, stack<pair<int, int>> c, int cl ) {
  vector<int> ansPossibilities = {};
  int ans = 0;
 
  int stick, stickIndex;
 
  //Ei ole viimeinen leikkaus
  if (cl != 0) {
    //Ensimmäinen leikkaus:
    if ((int)c.size() == 0) {
      stick = 0, stickIndex = -1;
    } else {
      pair<int, int> lastCut = c.top();
      stick = lastCut.first, stickIndex = lastCut.second;
    }
    //Loop through sticks
    for (int i = stick; i < (int)a.size(); i++) {
      //Loop through integer lengths in stick.
      // Calculate max non-mirror lengths.
      int start = 0, end = 0;
      if (i != stick) {
        start = 0;
        end = a[i]-1;
      } else {
        int cuts = a[i]-1;
        int maxLength = cuts;
        if ((cuts-(stickIndex+1)) % 2 == 0) {
          maxLength = (cuts-(stickIndex+1))/2;
        } else {
          maxLength = ceil((cuts-(stickIndex+1))/2.0);
        }
        start = stickIndex+1, end = stickIndex+maxLength+1;
      }
      for (int j = start; j < end; j++) {
        pair<int, int> temp;
        temp.first = i;
        temp.second = j;
        c.push(temp);
        ansPossibilities.push_back(recursiveCutting(a, c, cl-1));
        c.pop();
      }
    }
    //Calculate smallest min and max difference.
    int min = 0;
    for (int i = 0; i < (int)ansPossibilities.size(); i++) {
      if (ansPossibilities[i] < min || min == 0) {
        min = ansPossibilities[i];
      }
    }
    ans = min;
  } else {
    //Calculate min and max difference.
    //cout << "= = = OPTION = = =" << "\n";
    vector<int> cuts = {};
    int currentStick = 0;
    int max = 0, min = 0;
    while (!c.empty()) {
      pair<int, int> cut = c.top();
      if (cut.first == currentStick) {
        cuts.push_back(cut.second);
        c.pop();
      }
      if (cut.first != currentStick || c.size() == 0){
        //cout << "Found all of same stick: " << cuts.size() << "\n";
        //cout << "Last of same stick: " << cuts[(int)cuts.size()-1] << "\n";
        int size = a[currentStick];
        //Go through all cuts that have been made on the stick.
        for (int i = (int)cuts.size()-1; i >= 0; i--) {
          //do the cuts and get min max of sticks, after that do max-min as ans
          // If last then check last 2
          int temp = cuts[i]+1-(a[currentStick]-size); 
          //cout << "temp: " << temp << " (cut: " << cuts[i] << ")" << "\n";
          if (i == 0) {
            int temp2 = size-temp; 
            if (temp2 > max || max == 0) {
              max = temp2;
            }
            if (temp2 < min || min == 0) {
              min = temp2;
            }
          }
          // create before variable for calculating chunk that has been cut off
          if (temp > max || max == 0) {
            max = temp;
          }
          if (temp < min || min == 0) {
            min = temp;
          }
          size -= temp;
        }
        cuts = {};
        currentStick++;
      }
      //cout << "(" << cut.first << ", " << cut.second << ")\n"; 
    }
    //cout << "max: " << max << " min: " << min << "\n";
    ans = max-min;
    //cout << "= = OPTION END = =" << "\n";
  }
  return ans;
}
 
vector<int> bruteForce13(int m, vector<int>& a) {
  vector<int> answer = {};
  for (int k = 1; k <= m; k++) {
    //cout << "================== " << "START " << k << " ==================" << "\n";
    stack<pair<int, int>> c;
    answer.push_back(recursiveCutting(a, c, k));
    //cout << "================== " << "END " << k << " ==================" << "\n";
  }
  return answer;
}
 
vector<int> bruteForce2(int n, int m, std::map<int, int> a) {
  vector<int> vastaus = {};
 
  int min = 0;
  int max = 0;
  for (const auto &pair : a) { 
    if (pair.first < min || min == 0) {
      min = pair.first;
    }
    if (pair.first > max || max == 0) {
      max = pair.first;
    }
  }
  for (int i = 1; i <= m; i++) { //Mennään läpi kaikki leikkaukset.
    a[max] -= 1;
    int half = floor(max/2); //tsek if al:wready does floor
    //split into equal parts, also do checks after each split? idk
    //
    if ((float)half != max/2.0) {
      a[half] += 1;
      a[half+1] += 1;
    } else {
      a[half] += 2;
    }
 
    min = 0;
    max = 0;
    for (const auto &pair : a) {
      if (pair.second != 0) {
        if (pair.first < min || min == 0) {
          min = pair.first;
        }
        if (pair.first > max || max == 0) {
          max = pair.first;
        }
      }
    }
    //for loopin jälkeen push back vastaukseen
    vastaus.push_back(max-min);
  }
  return vastaus;
}
 
int main() {
  int n, m;
  vector<int> a;
  int maxA = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int temp;
    cin >> temp;
    if (temp > maxA) {
      maxA = temp;
    }
    a.push_back(temp);
    /*if (a[i].second > 0) {
      a[i].second += 1;
    } else {
      a[i].first = temp;
      a[i].second = 1;
    }*/
  }
  vector<int> vastaukset = {}; 
  /*if (maxA <= 3) {
    vastaukset = bruteForce2(n, m, a);
  } else {
    vastaukset = bruteForce13(m, a);
  }*/
  vastaukset = bruteForce13(m, a);
  for (int i = 0; i < (int)vastaukset.size(); i++) {
    cout << vastaukset[i] << " ";
  }
}
 
 

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: RUNTIME ERROR

Test 3

Group: 1, 4, 5, 6

Verdict: RUNTIME ERROR

Test 4

Group: 1, 4, 5, 6

Verdict: RUNTIME ERROR

Test 5

Group: 2, 5, 6

Verdict: RUNTIME ERROR

Test 6

Group: 2, 5, 6

Verdict: RUNTIME ERROR

Test 7

Group: 3, 5, 6

Verdict: RUNTIME ERROR

Test 8

Group: 3, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 5, 6

Verdict: RUNTIME ERROR

Test 12

Group: 4, 5, 6

Verdict: RUNTIME ERROR

Test 13

Group: 4, 5, 6

Verdict: RUNTIME ERROR

Test 14

Group: 4, 5, 6

Verdict: RUNTIME ERROR

Test 15

Group: 4, 5, 6

Verdict: RUNTIME ERROR

Test 16

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED