154

Main.java

import java.io.InputStream;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;
import java.io.BufferedReader;
import java.util.Collections;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.Arrays;
 
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Artem Gilmudinov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream;
        try {
            outputStream = new FileOutputStream("output.txt");
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        Reader in = new Reader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }
 
    static class Task {
        final int size = 100000;
        final int b = 10000;
        ArrayList<Integer> cubes;
        ArrayList<Integer> nums;
        Comparator<Integer> cmp = new Comparator<Integer>() {
 
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        };
 
        public void solve(int testNumber, Reader in, PrintWriter out) {
 
            int n = in.ni();
            if (n == 23 || n == 239) {
                out.println("IMPOSSIBLE");
                return;
            }
            cubes = new ArrayList<>();
            nums = new ArrayList<>();
            for (int i = 0; ; i++) {
                if (i * i * i <= n) {
                    cubes.add(i * i * i);
                    nums.add(i);
                } else {
                    break;
                }
            }
            byte[] dp = new byte[size + 1];
            int[] s = new int[size + 1];
            byte[] prev = new byte[size + 1];
            Arrays.fill(prev, Byte.MAX_VALUE);
            Arrays.fill(dp, Byte.MAX_VALUE);
            prev[0] = dp[0] = 0;
            int t, v;
            for (int z = 0; z < cubes.size(); z++) {
                int cube = cubes.get(z);
                if (cube > size) {
                    continue;
                }
                for (int j = 0; j < 8; ++j) {
                    v = size - cube;
                    for (int i = 0; i <= v; ++i) {
                        if (prev[i] < 8) {
                            t = i + cube;
                            if (prev[i] + 1 < dp[t]) {
                                dp[t] = (byte) (prev[i] + 1);
                                s[t] = z;
                            }
                        }
                    }
                    for (int i = 0; i <= size; ++i) {
                        prev[i] = dp[i];
                    }
                }
            }
            if (n <= size) {
                ArrayList<Integer> decomposition = getDecomposition(n, s);
                Collections.sort(decomposition, cmp);
                for (Integer x : decomposition) {
                    out.print(x + " ");
                }
                out.println();
            } else {
                int x = findNearestCube(n);
                ArrayList<Integer> res = new ArrayList<>();
                res.add(x);
                int diff = n - cubes.get(x);
                if (diff <= size) {
                    res.addAll(getDecomposition(diff, s));
                } else {
                    x = findNearestCube(diff);
                    res.add(x);
                    res.addAll(getDecomposition(diff - cubes.get(x), s));
                }
                Collections.sort(res, cmp);
                for (Integer u : res) {
                    out.print(u + " ");
                }
            }
        }
 
        ArrayList<Integer> getDecomposition(int n, int[] s) {
            ArrayList<Integer> res = new ArrayList<>();
            while (n != 0) {
                res.add(s[n]);
                n -= cubes.get(s[n]);
            }
            return res;
        }
 
        int findNearestCube(int x) {
            int res = 0;
            for (int i = 0; i < cubes.size(); i++) {
                if (cubes.get(i) <= x && x - cubes.get(i) >= b) {
                    res = i;
                }
            }
            return res;
        }
 
    }
 
    static class Reader {
        private BufferedReader in;
        private StringTokenizer st = new StringTokenizer("");
        private String delim = " ";
 
        public Reader(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }
 
        public String next() {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(rl());
            }
            return st.nextToken(delim);
        }
 
        public String rl() {
            try {
                return in.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
 
        public int ni() {
            return Integer.parseInt(next());
        }
 
    }
}

Я приведу своё решение.

Будем считать динамику dp[i] = минимальное количество кубов в которое раскладывается число i.
Для восстановления этих кубов заведём массив s[i], в котором будем хранить какой последний куб был добавлен.
Посчитаем статистику cnt[i], где 0<=i<=8 и cnt[i] = количество чисел которое минимальным образом раскладывается в i кубов.

Приведу эти значения:
n = 1000 [0, 10, 41, 122, 242, 293, 202, 73, 15]
n = 10000 [0, 21, 202, 1129, 3343, 3842, 1325, 121, 15]
n = 100000 [0, 46, 938, 10678, 46684, 38076, 3440, 121, 15]
n = 1000000 [0, 100, 4354, 103421, 605489, 282579, 3919, 121, 15]

Замечаем что числа которые минимально раскладываются в только 8 кубов, закончились на 1000.
А числа раскладывающиеся минимум в 7 кубов закончились на 10000.

Предпосчитаем нашу динамику, предположим, для 10^5.

Если n <= 10^5, то выводим ответ.
Если n > 10^5. Пытаемся найти ближайший меньший куб, который на расстоянии больше чем 10^4.
Если мы нашли такой куб и расстояние меньше чем 10^5, то выводим ответ (максимум разложили в 7 кубов).
Если расстояние больше чем 10^5, то мы вынуждены ещё раз найти ближайший куб для этого расстояния (с тем же условием что разница больше чем 10^4, дабы гарантировать что мы разложим расстояние в максимум 6 кубов).
В итоге 8 кубов в худшем случае. Можно доказать, что нам всего лишь два раза придётся искать ближайший куб.

Основное время занимает динамика в 8 * pow(10^5, 1/3) *10^5