#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,

Good test:

16
0 0
3 0
3 1
4 1
4 0
7 0
7 2
6 2
6 1
5 1
5 2
2 2
2 1
1 1
1 2
0 2

My AC program prints 7.000000

Another test:

13
1 1
3 1
3 3
5 3
5 5
3 5
4 4
2 4
2 2
1 3
0 3
0 0
1 0

Answer:
7.071068

If your program has O(n^2*log(n)) time complexity or faster try the following tests:

10
4 10
0 0
5 0
5 3
13 3
10 8
5 8
7 5
2 1
5 10

Answer:
12.276044

24
13 10
11 17
7 20
1 20
1 11
13 0
23 7
23 19
14 22
20 18
18 11
13 6
5 15
13 4
20 8
13 3
8 7
3 14
3 17
6 17
13 8
17 17
11 20
14 17

Answer:
20.645581

29
17 13
11 12
10 10
12 6
22 6
23 13
12 18
0 14
12 1
14 2
7 12
12 15
20 13
18 10
12 10
19 8
21 13
12 16
5 13
12 3
2 14
12 17
22 13
21 7
12 7
11 10
19 13
13 14
10 13

Answer:
18.193976

Edited by author 25.08.2019 17:28

Is it really needed to set 4mb memory limit?
I really must to remember pascal for this task, because the same solution have TL (not a Scanner) or ML on java.
May be it's possible to up memory limit to 8mb?

#include<bits/stdc++.h>
using namespace std;
const long long size=65535;
long long ara[size];
long long b[size];
Find()
{
    long long i, sum=1, j;
    for(i=0, j=1; i<=size; i++, j++)
    {
        sum=sum+i;
        ara[j]=sum;

    }

}
int main()
{
    long long i, n, a, r, j;
    Find();
    cin>>a;
    for(i=1; i<=a; i++)
    {
        cin>>b[i];
    }
    for(i=1; i<=a; i++)
    {
        r=0;

        for(j=1; j<=size; j++)
        {
            if(b[i]==ara[j])
            {
                r=1;
                break;
            }
        }
        if(r==1)
        {
            printf("1 ");
        }
        else
        {
            printf("0 ");
        }


    }
    printf("\n");

    return 0;
}

Code removed

Edited by author 20.08.2019 21:12

I can't understand how to solve the problem with Python and meet time limitations. I implemented solution with creating 3-D list of subsumes[column][row_start][row_offset] using accumulate from itertools and list comprehension.

After that I used Kadane's algorithm. I expect that it works with O(N^3). But it isn't enough...

Are there some tricks in the problem for Python? Except for stdin of course.

t = int(input())
for i in range(t):
    m = []
    kv = 0
    n,k = map(int,input().split())
    ok =k
    for i in range (k):
        if i == 0:
            m.append(n//ok)
            kv += m[i]
            n-=n//ok
            ok-=1
        else:
            if i == k-1:
                m.append(n)
            else:
                m.append(n//ok)
                kv+=m[i]
                n-=n//ok
                ok-=1
    otr,ans = 0,0
    l,l1 = 0,0
    m.sort()
    m.reverse()
    ss = sum(m)
    for i in range(k-1):
        l += m[i]
        l1 = m[i]
        ans += (ss-l)*l1
    print(ans)