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

My Endlish is not that good, could anyone translate it into Russian, pls?

inputs of the third test?

Try this test

inp
901000

ans
910000

I run out of ideas, trying to pass test #5. Does anyone can tell me how this test looks like?
Thank you,