This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <array>
#include <vector>
#define ll long long
using namespace std;
ll n, m, a, f, mask, cnt[20], A[300000];
vector <ll> V[21];
array <array<ll, 2>, 2> dp[(1LL<<20)];
void add(ll u, array<ll, 2> x) {
if (dp[u][0][0] < x[0]) dp[u][1] = dp[u][0], dp[u][0] = x;
else if (dp[u][1][0] < x[0] && dp[u][0][1] != x[1]) dp[u][1] = x;
}
int main() {
cin >> n >> m;
for (int i=0; i<(1LL<<20); ++i) {
dp[i] = {0, -1, 0, -1};
V[__builtin_popcount(i)].push_back(i);
}
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
cin >> a;
cnt[j] += a;
A[i] += a<<j;
}
add(A[i] ^ (((1LL<<m)-1)), {__builtin_popcount(A[i] ^ ((1LL<<m)-1)), i});
}
for (int i=20; i>1; --i) {
for (auto u : V[i]) {
for (int j=0; j<20; ++j) {
if (u & (1LL<<j)) {
add(u-(1LL<<j), {dp[u][0][0]-1, dp[u][0][1]});
add(u-(1LL<<j), {dp[u][1][0]-1, dp[u][1][1]});
}
}
}
}
for (int i=1; i<20; ++i) {
for (auto u : V[i]) {
for (int j=0; j<20; ++j) {
if (!(u & (1LL<<j))) {
add(u+(1LL<<j), dp[u][0]);
add(u+(1LL<<j), dp[u][1]);
}
}
}
}
for (int i=0; i<n; ++i) {
f = mask = 0;
for (int j=0; j<20; ++j) {
a = cnt[j]-(bool)(A[i] & (1LL<<j));
if (a > n/2) ++f;
else if (a == n/2) mask += (1LL<<j);
}
if (dp[mask][0][1] != i) f += dp[mask][0][0];
else f += dp[mask][1][0];
cout << f << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |