2e-ambitious-snail.js

/*

E. Амбициозная улитка

Ограничение времени	5 секунд (фактическое использование на тестах – до 0.605s)
Ограничение памяти	256Mb (фактическое использование на тестах – до 73.45Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Домашний питомец мальчика Васи — улитка Петя. Петя обитает на бесконечном в обе стороны вертикальном столбе, который для удобства можно представить как числовую прямую. Изначально Петя находится в точке 0.

Вася кормит Петю ягодами. У него есть n ягод, каждая в единственном экземпляре. Вася знает, что если утром он даст Пете ягоду с номером i, то поев и набравшись сил, за остаток дня Петя поднимется на a[i] единиц вверх по столбу, но при этом за ночь, потяжелев, съедет на b[i] единиц вниз. Параметры различных ягод могут совпадать.

Пете стало интересно, а как оно там, наверху, и Вася взялся ему в этом помочь. Ближайшие n дней он будет кормить Петю ягодами из своего запаса таким образом, чтобы максимальная высота, на которой побывал Петя за эти n дней была максимальной. К сожалению, Вася не умеет программировать, поэтому он попросил вас о помощи. Найдите, максимальную высоту, на которой Петя сможет побывать за эти n дней и в каком порядке Вася должен давать Пете ягоды, чтобы Петя смог её достичь!

Формат ввода
В первой строке входных данных дано число n (1 ≤ n ≤ 5 ⋅ 10^5) — количество ягод у Васи. В последующих n строках описываются параметры каждой ягоды. В i+1 строке дано два числа a[i] и b[i] (0 ≤ a[i], b[i] ≤ 10^9) — то, насколько поднимется улитка за день после того, как съест i ягоду и насколько опуститься за ночь.

Формат вывода
В первой строке выходных данных выведите единственное число — максимальную высоту, которую сможет достичь Петя, если Вася будет его кормить оптимальным образом. В следующей строке выведите n различных целых чисел от 1 до n — порядок, в котором Вася должен кормить Петю (i число в строке соответствует номеру ягоды, которую Вася должен дать Пете в i день чтобы Петя смог достичь максимальной высоты).

Пример 1

Ввод
3
1 5
8 2
4 4

Вывод
10
2 3 1 

Пример 2

Ввод
2
7 6
7 4

Вывод
10
2 1 

Примечания
Во втором примере изначально улитка находится на высоте 0. Пусть сначала Петя накормит её второй ягодой, а затем первой. После того как она съест вторую ягоду, за день она поднимется на 7 (и окажется на высоте 7), а за ночь опустится на 4 (и окажется на высоте 3). После того как она съест первую ягоду, за день она поднимется на 7 (и окажется на высоте 10), а за ночь опустится на 6 (и окажется на высоте 4).
Таким образом, максимальная высота, на которой побывает улитка при данном порядке кормления, равна 10. Нетрудно видеть, что если Петя накормит улитку сначала первой ягодой, а затем второй, то максимальная высота, на которой побывает улитка, будет меньше.

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim() + '\n';
const length = input.length;

let listStarted = false;
let pairCount = 0;
let parsingSecondValue = false;
let firstValueString = '';
let firstValueNumber = 0;
let secondValueString = '';
let secondValueNumber = 0;
let positivePairIndexes = [];
let negativePairIndexes = [];
let maxClimbValue = 0;

let bestPositiveCandidate = false;

let bestPositivePairClimb = 0;
let bestPositivePairFall = 0;
let bestPositivePairSum = Infinity;
let bestPositivePairIndex = -1;

let secondBestPositivePairClimb = 0;
let secondBestPositivePairFall = 0;
let secondBestPositivePairSum = Infinity;
let secondBestPositivePairIndex = -1;

let worstPositiveCandidate = false;

let worstPositivePairClimb = 0;
let worstPositivePairFall = 0;
let worstPositivePairSum = Infinity;
let worstPositivePairIndex = -1;

let secondWorstPositivePairClimb = 0;
let secondWorstPositivePairFall = 0;
let secondWorstPositivePairSum = Infinity;
let secondWorstPositivePairIndex = -1;

let bestNegativePairClimb = 0;
let bestNegativePairIndex = -1;

function setBestPositive() {
    if (secondBestPositivePairIndex !== -1 && secondBestPositivePairIndex !== worstPositivePairIndex && secondBestPositivePairIndex !== secondWorstPositivePairIndex) {
        if (secondBestPositivePairSum !== Infinity) {
            maxClimbValue += secondBestPositivePairSum;
        }
        positivePairIndexes.push(secondBestPositivePairIndex);
    }

    secondBestPositivePairClimb = bestPositivePairClimb;
    secondBestPositivePairFall = bestPositivePairFall;
    secondBestPositivePairSum = bestPositivePairSum;
    secondBestPositivePairIndex = bestPositivePairIndex;

    bestPositivePairClimb = firstValueNumber;
    bestPositivePairFall = secondValueNumber;
    bestPositivePairSum = firstValueNumber - secondValueNumber;
    bestPositivePairIndex = pairCount;
}

function setWorstPositive() {
    if (secondWorstPositivePairIndex !== -1 && secondWorstPositivePairIndex !== bestPositivePairIndex && secondWorstPositivePairIndex !== secondBestPositivePairIndex) {
        if (secondWorstPositivePairSum !== Infinity) {
            maxClimbValue += secondWorstPositivePairSum;
        }
        positivePairIndexes.push(secondWorstPositivePairIndex);
    }

    secondWorstPositivePairClimb = worstPositivePairClimb;
    secondWorstPositivePairFall = worstPositivePairFall;
    secondWorstPositivePairSum = worstPositivePairSum;
    secondWorstPositivePairIndex = worstPositivePairIndex;

    worstPositivePairClimb = firstValueNumber;
    worstPositivePairFall = secondValueNumber;
    worstPositivePairSum = firstValueNumber - secondValueNumber;
    worstPositivePairIndex = pairCount;
}

for (let i = 0; i < length; ++i) {
    if (input[i] === '\n') {
        if (listStarted === false) {
            listStarted = true;
            firstValueString = '';
            secondValueString = '';
            parsingSecondValue = false;
        } else {
            ++pairCount;
            firstValueNumber = parseInt(firstValueString);
            secondValueNumber = parseInt(secondValueString);

            bestPositiveCandidate = firstValueNumber > bestPositivePairClimb ||
                (firstValueNumber === bestPositivePairClimb && firstValueNumber - secondValueNumber < bestPositivePairSum);

            worstPositiveCandidate = secondValueNumber > worstPositivePairFall ||
                (secondValueNumber === worstPositivePairFall && firstValueNumber - secondValueNumber < worstPositivePairSum);

            if (firstValueNumber - secondValueNumber > 0) {
                if (bestPositiveCandidate || worstPositiveCandidate) {
                    if (bestPositiveCandidate) {
                        setBestPositive();
                    }
                    if (worstPositiveCandidate) {
                        setWorstPositive();
                    }
                } else {
                    maxClimbValue += firstValueNumber - secondValueNumber;
                    positivePairIndexes.push(pairCount);
                }
            } else {
                if (firstValueNumber > bestNegativePairClimb) {
                    if (bestNegativePairIndex !== -1) {
                        negativePairIndexes.push(bestNegativePairIndex);
                    }
                    bestNegativePairClimb = firstValueNumber;
                    bestNegativePairIndex = pairCount;
                } else {
                    negativePairIndexes.push(pairCount);
                }
            }

            firstValueString = '';
            secondValueString = '';
            parsingSecondValue = false;
        }
    } else if (input[i] === ' ') {
        parsingSecondValue = true;
    } else {
        if (parsingSecondValue === false) {
            firstValueString += input[i];
        } else {
            secondValueString += input[i];
        }
    }
}

const selectedPositivePairsData = new Map();
selectedPositivePairsData.set(bestPositivePairIndex, [bestPositivePairClimb, bestPositivePairFall]);
selectedPositivePairsData.set(worstPositivePairIndex, [worstPositivePairClimb, worstPositivePairFall]);
selectedPositivePairsData.set(secondBestPositivePairIndex, [secondBestPositivePairClimb, secondBestPositivePairFall]);
selectedPositivePairsData.set(secondWorstPositivePairIndex, [secondWorstPositivePairClimb, secondWorstPositivePairFall]);

const firstIndexSequence = [];
const secondIndexSequence = [];

if (bestPositivePairIndex !== worstPositivePairIndex) {
    firstIndexSequence.push(secondBestPositivePairIndex, secondWorstPositivePairIndex, bestPositivePairIndex, worstPositivePairIndex);
} else {
    if (bestPositivePairIndex !== secondWorstPositivePairIndex) {
        firstIndexSequence.push(secondBestPositivePairIndex, worstPositivePairIndex, bestPositivePairIndex, secondWorstPositivePairIndex);
    }

    if (secondBestPositivePairIndex !== worstPositivePairIndex) {
        secondIndexSequence.push(secondWorstPositivePairIndex, bestPositivePairIndex, secondBestPositivePairIndex, worstPositivePairIndex);
    }
}

const thirdIndexSequence = [];
const fourthIndexSequence = [];

if (bestPositivePairIndex !== worstPositivePairIndex) {
    thirdIndexSequence.push(secondBestPositivePairIndex, secondWorstPositivePairIndex, worstPositivePairIndex, bestPositivePairIndex);
} else {
    if (worstPositivePairIndex !== secondBestPositivePairIndex) {
        thirdIndexSequence.push(bestPositivePairIndex, secondWorstPositivePairIndex, worstPositivePairIndex, secondBestPositivePairIndex);
    }

    if (secondWorstPositivePairIndex !== bestPositivePairIndex) {
        fourthIndexSequence.push(secondBestPositivePairIndex, worstPositivePairIndex, secondWorstPositivePairIndex, bestPositivePairIndex);
    }
}


function getFilteredSequence(sequence) {
    const filteredSequence = [];
    for (let i = sequence.length - 1; i >= 0; --i) {
        if (sequence[i] !== -1 && filteredSequence.indexOf(sequence[i]) === -1) {
            filteredSequence.unshift(sequence[i]);
        }
    }
    return filteredSequence;
}

const filteredFirstIndexSequence = getFilteredSequence(firstIndexSequence);
const filteredSecondIndexSequence = getFilteredSequence(secondIndexSequence);
const filteredThirdIndexSequence = getFilteredSequence(thirdIndexSequence);
const filteredFourthIndexSequence = getFilteredSequence(fourthIndexSequence);

function getSequenceMaxSum(sequence) {
    let sequenceSum = maxClimbValue;
    let sequenceMax = 0;
    for (const index of sequence) {
        const [climb, fall] = selectedPositivePairsData.get(index);
        sequenceSum += climb;
        sequenceMax = Math.max(sequenceMax, sequenceSum);
        sequenceSum -= fall;
    }

    return [sequenceMax, sequenceSum];
}

const [firstCaseMax, firstCaseSum] = getSequenceMaxSum(filteredFirstIndexSequence);
const [secondCaseMax, secondCaseSum] = getSequenceMaxSum(filteredSecondIndexSequence);
const [thirdCaseMax, thirdCaseSum] = getSequenceMaxSum(filteredThirdIndexSequence);
const [fourthCaseMax, fourthCaseSum] = getSequenceMaxSum(filteredFourthIndexSequence);

const positiveMax = Math.max(firstCaseMax, secondCaseMax, thirdCaseMax, fourthCaseMax);

function getBestSequenceData() {
    if (positiveMax === firstCaseMax) {
        return [filteredFirstIndexSequence, firstCaseSum];
    } else if (positiveMax === secondCaseMax) {
        return [filteredSecondIndexSequence, secondCaseSum];
    } else if (positiveMax === thirdCaseMax) {
        return [filteredThirdIndexSequence, thirdCaseSum];
    } else if (positiveMax === fourthCaseMax) {
        return [filteredFourthIndexSequence, fourthCaseSum];
    }
}

const [middlePairIndexes, middlePairSum] = getBestSequenceData();

let negativeSum = middlePairSum;
let negativeMax = 0;
negativeSum += bestNegativePairClimb;
negativeMax = Math.max(negativeMax, negativeSum);
if (bestNegativePairIndex !== -1) {
    middlePairIndexes.push(bestNegativePairIndex);
}

let bestMax = Math.max(positiveMax, negativeMax);

fs.writeFileSync('output.txt', `${bestMax}\n${(positivePairIndexes.join(' ') + ' ' + middlePairIndexes.join(' ') + ' ' + negativePairIndexes.join(' ')).trim()}`);