dyn-prog-static-fields-lists

import java.io.*;
import java.util.*;

public class Solution {

    static int[] p;

    static int[] deltas = new int[] {1, 2, 5};

    static List<Integer> /*int[]*/ r;

    static List<Integer> /*int[]*/ s;

    static void fillP(int n) {
        p = new int[n];
        p[0] = 1;
        for (int i = 0; i < n-1; ++i) {
            p[i+1] = p[i] + deltas[i % deltas.length];
        }
    }

    static int rodCutBottomUp(int n) {
        r = new ArrayList<Integer>(n);
        s = new ArrayList<Integer>(n);
        r.add(0, 0);
        s.add(0, 0);
        for (int rod = 1; rod <= n; ++rod) {
            int max = -1;
            int imax = -1;
            for (int len = 1; len <= rod; ++len) {
                int price = p[len-1] + r.get(rod - len);
                if (max < price) {
                    max = price;
                    imax = len;
                }
            }
            r.add(rod, max);
            s.add(rod, imax);
        }
        return r.get(n);
    }

    public static void main(String[] args) throws IOException {
        int n = 100000;
        fillP(n);
        long start = System.currentTimeMillis();
        System.out.println(rodCutBottomUp(n));
        System.out.println("time bu: " + (System.currentTimeMillis() - start));
    }
}