I've tried priority_queue and heap, but still MLE. Here's my code, can somebody help me?
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
    int n, a;
    std::cin >> n;
    std::vector<int> v(n / 2 + 1);
    for (int i = 0; i < n / 2 + 1; ++i) {
        std::cin >> v[i];
    }
    std::make_heap(v.begin(), v.end());
    for (int i = 0; i < (n + 1) / 2 - 1; ++i) {
        std::cin >> a;
        v.push_back(a);
        std::push_heap(v.begin(), v.end());
        std::pop_heap(v.begin(), v.end());
        v.pop_back();
    }
    std::sort_heap(v.begin(), v.end());
    if (n % 2) {
        std::cout << v.back() << ".0";
    }
    else {
        a = v.back();
        v.pop_back();
        std::cout << (0ll + a + v.back()) / 2 << '.';
        if ((0ll + a + v.back()) % 2) {
            std::cout << 5;
        }
        else {
            std::cout << 0;
        }
    }

    return 0;
}

Count numbers bigger than a[i] from 0..i-1 ans smaller than a[i] from i+1..n-1 ans then try to build the answer :)

It is around 70


Edited by author 09.09.2019 22:01

[code deleted]


Edited by author 08.09.2019 10:26

Edited by moderator 19.11.2019 23:32

OMG, standart interval tree gives TLE 6. It's terrible! Why?!

Please, could you send your problem(AC code)

Please, could you send your problem(AC code)

Edited by author 09.09.2019 23:30

49 3
I mean, FRRR or FLLL or FLFLLF could return us to the base,
it also doesn't violate any of two rules:
1. The total number of letters F must not exceed S and 2. the total number of letters L and R must not exceed T

are there any more restrictions???

#include <iostream>
using namespace std;

int main() {

    int n, k;
    cin >> n >> k;
    int c = n * k;
    int *arr = new int[k];

    for (int i = 0; i < k; i++) {
        cin >> arr[i];
        c = c - arr[i];
    }

    cout << abs(c);

}

Could anybody help me? I have WA at 4th test!

Ok, I've found relation between n and maximin palindrome number and several optimal patterns that depend on n mod 12. Only one question has left: how to prove all this stuff?

How to treat cameras, located on the starting and/or finish line? Do racers interact with them?

Cannot break this case. Any hint?

What is algorithm? What formulas, theorems, equations and hints must I use?

My code is as following:
#include<iostream>
#include<vector>
using namespace std;

long getMaxSumRow(long rowArr[], int n) {
    long cs = 0;
    long ms = 0;
    bool positiveNumberPresent = false;

    for (int i = 0; i < n; i++) {
        if (!positiveNumberPresent && (rowArr[i] >= 0)) {
            positiveNumberPresent = true;
        }
        cs += rowArr[i];

        if (cs < 0) {
            cs = 0;
            continue;
        }

        if (cs > ms) {
            ms = cs;
        }
    }

    if (positiveNumberPresent) {
        return ms;
    }

    ms = rowArr[0];

    for (int i = 0; i < n; i++) {
        if (rowArr[i] > ms) {
            ms = rowArr[i];
        }
    }

    return ms;
}

long maxSumRec(vector<vector<long> > &arr, int n) {
    if (n == 1) {
        return arr[0][0];
    }

    /* Take an array for running rows sum */
    long runningRowSum[n];

    for (int r = 0; r < n; r++) {
        runningRowSum[r] = 0;
    }

    long maxSum = INT_MIN;

    /* Initialize variables for left-right and top-bottom bounds */
    int left, right, top = 0, bottom = n-1;

    /* Iterate from all possible lefts to all possibe rights ahead of this left */
    for (left = 0; left < n; left++) {
        for (right = 0; right < n; right++) {
            for (top = 0; top <= bottom; top++) {
                runningRowSum[top] += arr[top][right];
            }
            /* For this left-right combination, calculate contigeous subarray with maximum sum in runningRowSum */
            long currSum = getMaxSumRow(runningRowSum, n);

            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        /* Reinitialize running row sum to 0 */
        for (int r = 0; r < n; r++) {
            runningRowSum[r] = 0;
        }
    }

    return maxSum;
}

int main() {
    int n;
    cin >> n;
    vector<vector<long> > arr(n);

    for (int i = 0; i < n; i++) {
        arr[i] = vector<long>(n);
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    cout << maxSumRec(arr, n);
    return 0;
}

But I am getting wrong answer for test case#3 . Any advice on what it might be failing at ?

3 4
1 2
1 3
4 5
4 6
ans:
1 5 6
2 3 4

Edited by author 03.09.2019 09:23

There cannot be any impossible case as is suggested by the very first line of the problem statement