## A Harder Contest '19 - An Alternating Problem

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Java 8 5.0s
Memory limit: 256M

Author:
Problem types

Given a array of integers and an integer , find a subsequence of this array such that the alternating sum of this subsequence is maximal, and the absolute difference between any two adjacent elements in the subsequence is at most .

If there are multiple solutions, print the lexicographically least.

An array is a subsequence of if can be obtained by deleting some of the elements in . It is not required to delete any elements.

We define the alternating sum of a subsequence as the result of adding each value at an odd index in the sequence (1-indexed), and subtracting each value at an even index in the sequence.

Imagine a sequence of length :

We define the alternating sum of as:         The inequality must hold for #### Input Specification

The first line will contain integers,  .

The second line will contain integers  .

#### Output Specification

On the first line, output a single integer, the maximum alternating sum you can obtain.

On the second line, output the indices (1-indexed) of the elements contained in the subsequence.  No further constraints.

#### Sample Input 1

4 3
-1 2 3 4

#### Sample Output 1

4
4

#### Explanation for Sample 1

The maximum alternating sum is simply , the only element included is at index 4.

#### Sample Input 2

5 100
3 -4 -2 -9 10

#### Sample Output 2

24
1 2 3 4 5

#### Explanation for Sample 2

The maximum alternating sum is , which can be obtained by choosing elements , , , and in your subsequence.

#### Sample Input 3

5 7
3 -4 -2 -9 10

#### Sample Output 3

14
1 2 3 4

#### Explanation for Sample 3

The maximum alternating sum is , which can be obtained by choosing elements , , and in your subsequence. Note that the result here differs from that of sample output two due to the constraint.