I know that the task was rejudged.
I added the condition for new test, where A, B and C collinear: cos(ACB) - 1.0 < eps, where eps = 1e-8, then answer = AB, but I've still get WA 48. Give me a hint, please.
Thanks in advance.

You should find the permutation with the maximum number of inversions. You can use segment tree to calculate inversions for each element, just store sorted leafes in each node.

Didn't know will it be useful for someone and is it on the right path to solve the problem, but I wish to publish this code for SSP solver. To invent good heuristics for MSSP is utmost harder.

using I = short;

template<typename T = I, typename S = I>
struct DDP // dynamic dynamic programming solver for subset sum problem O(n^3 * 2^sqrt(n)) (n is number of input bits)
{
    T terms[2][10001];
    S sums[2][10001];

    template<typename Term, typename Sum>
    std::pair<Term, Sum> solve(const Term termsBeg, const Term termsEnd, const Sum sumsBeg, const Sum sumsEnd)
    {
        static_assert(std::is_same<typename std::iterator_traits<Term>::value_type, T>::value, "!");
        static_assert(std::is_same<typename std::iterator_traits<Sum>::value_type, S>::value, "!");

        auto sumMax = std::max_element(sumsBeg, sumsEnd);

        auto termsSrc = terms[0];
        auto termsDst = terms[1];

        auto sumsSrc = sums[0];
        auto sumsDst = sums[1];

        *termsSrc = {};
        *sumsSrc = {};

        auto sumsSrcEnd = std::next(sumsSrc);
        for (auto t = termsBeg; t != termsEnd; ++t) {
            auto termsSrcBeg = termsSrc;
            auto termsDstBeg = termsDst;

            auto sumsSrcBeg = sumsSrc;
            auto sumsShiftedBeg = sumsSrc;
            auto sumsDstBeg = sumsDst;

            // merge unique
            assert(std::size_t(std::distance(sumsSrcBeg, sumsSrcEnd)) <= std::extent<std::remove_reference_t<decltype(sums[0])>>::value);
            while (sumsSrcBeg != sumsSrcEnd) {
                if (sumsShiftedBeg == sumsSrcEnd) {
                    break;
                }
                I shiftedSum = *sumsShiftedBeg + *t;
                if (shiftedSum < *sumsSrcBeg) {
                    *sumsDstBeg++ = shiftedSum;
                    ++sumsShiftedBeg;
                    *termsDstBeg++ = *t;
                } else {
                    if (shiftedSum == *sumsSrcBeg) {
                        ++sumsShiftedBeg;
                        assert(*sumsShiftedBeg + *t != *sumsSrcBeg);
                    }
                    *sumsDstBeg++ = *sumsSrcBeg++;
                    *termsDstBeg++ = *termsSrcBeg++;
                }
                assert(std::size_t(std::distance(sumsDst, sumsDstBeg)) <= std::extent<std::remove_reference_t<decltype(sums[0])>>::value);
            }
            if (sumsShiftedBeg == sumsSrcEnd) {
                sumsSrcEnd = std::copy(sumsSrcBeg, sumsSrcEnd, sumsDstBeg);
                termsDstBeg = std::copy_n(termsSrcBeg, std::distance(sumsDstBeg, sumsSrcEnd), termsDstBeg);
            } else {
                assert(sumsSrcBeg == sumsSrcEnd);
                sumsSrcEnd = std::transform(sumsShiftedBeg, sumsSrcEnd, sumsDstBeg, [t] (S s) { return s + *t; });
                termsDstBeg = std::fill_n(termsDstBeg, std::distance(sumsDstBeg, sumsSrcEnd), *t);
            }

            std::swap(termsSrc, termsDst);
            std::swap(sumsSrc, sumsDst);

            for (auto sum = sumsBeg; sum != sumsEnd; ++sum) {
                sumsSrcBeg = std::lower_bound(sumsSrc, sumsSrcEnd, *sum);
                if ((sumsSrcBeg != sumsSrcEnd) && (*sumsSrcBeg == *sum)) {
                    sumsSrcEnd = sumsSrcBeg;
                    assert((*std::next(termsSrc, std::distance(sumsSrc, sumsSrcEnd)) == *t));
                    auto termsDstEnd = termsDst;
                    do {
                        auto term = *std::next(termsSrc, std::distance(sumsSrc, sumsSrcEnd));
                        *termsDstEnd++ = term;
                        sumsSrcEnd = std::lower_bound(sumsSrc, sumsSrcEnd, *sumsSrcEnd - term);
                    } while (sumsSrcEnd != sumsSrc);
                    assert((std::accumulate(termsDst, termsDstEnd, S{}) == *sum));
                    termsDstBeg = termsDst;
                    auto termsSrcEnd = t;
                    assert(*termsSrcEnd == *termsDstBeg);
                    auto termsTail = termsSrcEnd;
                    while (++termsDstBeg != termsDstEnd) {
                        while (*--termsSrcEnd != *termsDstBeg) {
                            *termsTail-- = *termsSrcEnd;
                        }
                    }
                    while (termsBeg != termsSrcEnd) {
                        *termsTail-- = *--termsSrcEnd;
                    }
                    assert(std::distance(termsBeg, termsTail) + 1 == std::distance(termsDst, termsDstEnd));
                    auto term = termsTail;
                    termsDstBeg = termsDst;
                    assert(termsDstBeg != termsDstEnd);
                    do {
                        *termsTail-- = *termsDstBeg++;
                    } while (termsDstBeg != termsDstEnd);
                    assert(termsTail == std::prev(termsBeg));
                    return {term, sum}; // not past the end element for found range but exactly last element
                }
            }
            sumsSrcEnd = std::lower_bound(sumsSrc, sumsSrcEnd, *sumMax); // crop
        }
        return {termsEnd, sumsEnd};
    }
};

auto x = solve(std::begin(ships), std::end(ships), std::cbegin(rows), std::cend(rows)) if succeeded, it gives rearranged ships range such, that range [std::begin(ships), x.first] is a solution and sum of all ships is *x.second. [std::begin(ships), std::end(ships)) still consists of exactly the same ships. If not succeeded then it return a pair of std::end(ships) and std::cend(rows)

Edited by author 11.06.2020 12:53

dp[n][k] = max{dp[n-1][k] or a[n], dp[n-1][k-1]}
any hints?? thank you.

Edited by author 18.01.2017 13:16

A simple way to solve is to begin with a value x which going to depend whether n % k == 0. and increase it by k until it becomes n. and of course on each step multiply it to your sum which is initially 1.

Are multiple '1' digits possible in the circle ? If yes , then will they produce separate click if they are currently in the window ?

Edited by author 05.11.2020 03:23

Edited by author 05.11.2020 03:23

Edited by author 05.11.2020 03:23

http://e-maxx.ru/algo/connected_components
You need to output number of components minus 1.
Tests:

4 4 0
3 4
1 2
3 1
2 4
0


1 0 0
0

6 0 0
5

6 5 1
1 2
1 4
2 5
3 6
4 5
1 2
1

6 5 0
1 2
1 4
2 5
3 6
4 5
1

6 3 4
1 2
2 3
4 5
2

6 4 0
1 3
3 4
4 6
5 6
1

Edited by author 04.11.2020 21:20

 longest palindromic substring is "kazak" itself. What am i missing ?

WHYYYYY
if u have same problem
solution is 3 4 5

The key to solve is that : Driver won't take less than offered, and Petr won't pay more than asked. So if you using a loop for example in each step a will be always min(a + b, c) and c will always be max(c - d, a)

What is test 23?

Very Easy Josephus's problem. Look it on geek for geeks

Let
0,1,2,..N-1     - outer door
N ..  2*N - 1   - 1-inner room doors
2*N .. 3N - 1   - 2-inner room doors
....
i*N  i*N + 1,  .. i*N + N-1   - i-th room doors

total  (K+1)*N  doors.

W[i][j] - minimum dist from i to j-th door, where  0 <= i,j < (K+1)*N

initially  W[i][i] = 0,  W[i][j] = inifinity  for i <> j.

read,  and set W[i][j] = 1   if there exists road from i to j doors.

-----------------
N times run following steps:

1. Floyd algorithm  for 0.. (K+1)*N - 1   doors.

2.
  for  1<= t <= K ,  0 <= i, j < N  update
        W[t*N + i][ t*N + j]  = min(W[t*N + i][t*N+j], W[i][j])
  Because  (t*N + i, t*N + j)  - is identical path as outer  (i,j) path.


Edited by author 31.10.2020 16:46

8 8
1 2 3 4 5 6 7 8
21

4 2
1 3
3

4 2
2 3
3

4 1
1
3

4 1
2
2

I have written the code the using user defined function thats why it has become much bigger.

#include<Stdio.h>
#include<math.h>
int Sn(int n);
int An(int a);
int main()
{
    int x;
    scanf("%d",&x);
    Sn(x);
}
int Sn(int n)
{
    int j;
    if(n==1) {An(1); printf("+1");}
    else { for(j=1;j<n;j++) printf("(");
        for(j=1;j<=n;j++)
       {if(j==1)
        {An(j);printf("+%d)",n);}
        else if(j!=n) {An(j);printf("+%d)",n-j+1);}
        else {An(j);printf("+1");}}}

}

 int An(int a)
{ int i,p;
    if(a==1)
   printf("sin(%d)",a);
   else
   {for(i=1;i<=a;i++)
       { p= pow(-1,i+1);
          if(i==1) printf("sin(%d",i);
          else if(p==1) printf("+sin(%d",i);
         else printf("-sin(%d",i);}
          for(i=0;i<a;i++) printf(")"); }
}

Edited by author 29.10.2020 21:19

Try this test:
input:
1
8
output:
1

Oddly enough, my solution printed "infinity" in this simple case, but was successful with first 35 tests

/*
* Author      : Arman Sykot
* Date & time : 28.10.2020 21:47:12 +06
*/

#include <bits/stdc++.h>
#define ll long long
#define the_flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

int main() {

    the_flash;

    int n;
    cin >> n;

    int arr[n][n];

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << arr[i - j][j] << " ";
        }
    }

    for (int i = n; i < 2 * n - 1; i++) {
        for (int j = n - 1; j >= i - (n - 1); j--)
            cout << arr[j][i - j] << " ";
    }

    cout << "\n";

    return 0;
}

If you are trying to flip signs on rectangles consider of using 1 request instead of many. :)