HackerEarth Friendship and diseases problem solution

In this HackerEarth Friendship and diseases problem solution You want to arrange k people at a table. The table has n rows and m columns. Some of the cells are free and some of them are blocked.

The score of the arrangement is based on two factors:

Friendship is always important, even with respect to disease. The ith person has a friendship value fi. A connected component of people with the sum of friendship value equal to s adds s*s to score. A connected component is a set of people adjacent to each other. Two people are adjacent if they share a side.

You need to take care of the health of people. The ith person has a danger value di. Two adjacent people i and j reduce the score by di x dj.

Your task is to print an arrangement with as high a score as possible. Note that you can drop a person and do not give him a seat at the table.

HackerEarth Friendship and diseases problem solution.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 5e5 + 14, B = 25;
int a[MAX_N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        ll ans = 0;
        for (int i = 0; i < B; ++i) {
            int l = 0;
            while (l < n && (a[l] >> i & 1))
                ++l;
            int r = n;
            while (r > l && (a[r - 1] >> i & 1))
                --r;
            ans += (l == n ? n * ll(n + 1) / 2 - 1 : (l + 1) * ll(n - r + 1) - 1) * (1 << i);
        }
        cout << ans << 'n';
    }
}

coding problems solutions