p482.ans1
======================
12
4
1 3 4 5

=================
p482.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int16_t MAX_HEIGHT = 101;
const int16_t MAX_PERIMETER = 5300;

int16_t n;
vector<int16_t> heights;

void read() {
    cin >> n;
    heights.resize(n);
    cin >> heights;
}

int16_t calculate_initial_perimeter(const vector<int16_t>& h) {
    int16_t perimeter = 2;
    for(int16_t i = 0; i < static_cast<int16_t>(h.size()) - 1; ++i) {
        perimeter += 2 + abs(h[i] - h[i + 1]);
    }

    perimeter += h[0] + h.back();
    return perimeter;
}

vector<int16_t> reconstruct_stolen_boards(
    const vector<vector<vector<int16_t>>>& dp, const vector<int16_t>& h,
    int16_t max_height_last_height, int16_t max_height_perimeter
) {
    vector<int16_t> stolen_boards;
    int16_t current_height = max_height_last_height;
    int16_t current_perimeter = max_height_perimeter;

    for(int16_t pos = static_cast<int16_t>(h.size()); pos > 0; --pos) {
        if(dp[pos][current_height][current_perimeter] ==
               dp[pos - 1][current_height][current_perimeter] + h[pos - 1] &&
           dp[pos - 1][current_height][current_perimeter] != -1) {
            stolen_boards.push_back(pos);
        } else {
            for(int16_t prev_height = 0; prev_height < MAX_HEIGHT;
                ++prev_height) {
                int16_t prev_perimeter =
                    current_perimeter - abs(prev_height - current_height) - 2;
                if(prev_perimeter >= 0 &&
                   dp[pos - 1][prev_height][prev_perimeter] ==
                       dp[pos][current_height][current_perimeter]) {
                    current_height = prev_height;
                    current_perimeter = prev_perimeter;
                    break;
                }
            }
        }
    }

    sort(stolen_boards.begin(), stolen_boards.end());
    return stolen_boards;
}

void solve() {
    // dp[pos][last_height][perimeter] = maximum total height of the boards
    // removed among the first pos boards, given that the rightmost kept board
    // has height last_height and the kept fence so far contributes perimeter
    // to the half-perimeter accounting (each kept board adds 2 for its top and
    // bottom plus the height difference to the previous kept board). For each
    // board we either steal it (add its height to the removed total, keeping
    // last_height and perimeter) or keep it (advance last_height and add the
    // perimeter contribution). The target is to maximise removed height while
    // the kept fence's perimeter stays at least half the original. We compute
    // the initial perimeter, set the target to ceil(initial / 2), pick the
    // best final state with perimeter + last_height >= target, then walk the
    // dp table backwards to recover which boards were stolen.

    vector<vector<vector<int16_t>>> dp(
        n + 1,
        vector<vector<int16_t>>(MAX_HEIGHT, vector<int16_t>(MAX_PERIMETER, -1))
    );
    dp[0][0][0] = 0;

    int16_t initial_perimeter = calculate_initial_perimeter(heights);
    int16_t target_perimeter = (initial_perimeter + 1) / 2;

    for(int16_t pos = 0; pos < n; ++pos) {
        for(int16_t last_height = 0; last_height < MAX_HEIGHT; ++last_height) {
            for(int16_t perimeter = 0; perimeter < MAX_PERIMETER; ++perimeter) {
                if(dp[pos][last_height][perimeter] == -1) {
                    continue;
                }

                int16_t new_height = heights[pos];
                dp[pos + 1][last_height][perimeter] = max<int16_t>(
                    dp[pos + 1][last_height][perimeter],
                    dp[pos][last_height][perimeter] + new_height
                );

                int16_t new_perimeter =
                    perimeter + abs(last_height - new_height) + 2;
                if(new_perimeter < MAX_PERIMETER) {
                    dp[pos + 1][new_height][new_perimeter] = max<int16_t>(
                        dp[pos + 1][new_height][new_perimeter],
                        dp[pos][last_height][perimeter]
                    );
                }
            }
        }
    }

    int16_t max_height = -1, max_height_perimeter = 0,
            max_height_last_height = 0;
    for(int16_t last_height = 0; last_height < MAX_HEIGHT; ++last_height) {
        for(int16_t perimeter = 0; perimeter < MAX_PERIMETER; ++perimeter) {
            if(perimeter + last_height >= target_perimeter &&
               dp[n][last_height][perimeter] > max_height) {
                max_height = dp[n][last_height][perimeter];
                max_height_perimeter = perimeter;
                max_height_last_height = last_height;
            }
        }
    }

    vector<int16_t> stolen_boards = reconstruct_stolen_boards(
        dp, heights, max_height_last_height, max_height_perimeter
    );

    cout << max_height << endl;
    cout << static_cast<int16_t>(stolen_boards.size()) << endl;
    for(int16_t index: stolen_boards) {
        cout << index << " ";
    }

    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p482.in1
======================
6
3 4 2 4 3 1

=================
statement.txt
======================
482. Impudent Thief
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



For most people Halloween evening is a time of having fun. But Mr. X chose the night after Halloween to commit a crime. He wants to get some boards to build a shed. And he decided to stole it from the fence of the neighbouring factory. But he wants to do it in such a way that nobody will notice boards loss. The fence consists of several boards with width, equal to 1, and integer heights (see picture). Mr. X is going to take some boards from the fence and then put the remaining boards together without changing their order to form a new fence. To be sure that noboby will notice the change, the perimeter of resulting fence should not be less than a half of the perimeter of initial fence. See picure description to understand the way of calculating fence's perimeter. With such constraint, Mr. X wants to maximize total height of extracted boards.




Perimeter of the fence is a perimeter of the figure, which is made by joining the rectangles corresponding to boards. For example, perimeter of the fence in the picture is marked bold and it's length is equal to 24.

Input
The first line contains integer number n (1 ≤ n ≤ 50) — number of boards in the fence. The second line contains n integer numbers hi — heights of the boards (1 ≤ hi ≤ 100). Boards are given from the leftmost one to the rightmost one.

Output
In the first line output s — maximal total height of some subset of the boards, which can be taken without violating the described rule. In the second line output k — number of boards in such subset. In the third line output k numbers of the boards which should be stolen. Boards are numbered starting from 1 as they appear in the input. Print numbers in any order. If there are multiple solutions, output any.

Example(s)
sample input
sample output
6
3 4 2 4 3 1
12
4
1 3 4 5

=================
