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


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';
}
}