| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 769602 | 2023-06-29T20:36:36 Z | MilosMilutinovic | Council (JOI23_council) | C++14 | 1251 ms | 90584 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int M = 21;
int n, m, a[N][M], b[N][M], v[N], cnt[M], bst[1 << M], ans[N];
void dfs(int i, int x) {
for (int j = 1; j <= m; j++) {
int ni = (i ^ (1 << j));
if (__builtin_popcount(bst[ni] & ni) > __builtin_popcount(x & ni)) {
bst[ni] = x;
dfs(ni, x);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cnt[j] += a[i][j];
}
}
int full_mask = 0;
for (int j = 1; j <= m; j++) {
full_mask += (1 << j);
}
for (int iter = 1; iter <= 2; iter++) {
for (int i = 1; i <= n; i++) {
v[i] = 0;
for (int j = 1; j <= m; j++) {
if (a[i][j] == 1) {
v[i] += (1 << j);
}
}
}
for (int i = 0; i < (1 << M); i++) {
bst[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cnt[j] -= a[i][j];
}
int msk = 0, good = 0;
for (int j = 1; j <= m; j++) {
if (cnt[j] == (n / 2)) {
msk ^= (1 << j);
}
if (cnt[j] >= (n / 2)) {
good += 1;
}
}
ans[iter == 1 ? i : n - i + 1] = max(ans[iter == 1 ? i : n - i + 1], good - __builtin_popcount(bst[msk] & msk));
for (int j = 1; j <= m; j++) {
cnt[j] += a[i][j];
}
dfs(full_mask ^ v[i], v[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[n - i + 1][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = b[i][j];
}
}
}
for (int i = 1; i <= n; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8532 KB | Output is correct |
| 2 | Correct | 6 ms | 8788 KB | Output is correct |
| 3 | Correct | 4 ms | 8532 KB | Output is correct |
| 4 | Correct | 4 ms | 8532 KB | Output is correct |
| 5 | Correct | 504 ms | 90584 KB | Output is correct |
| 6 | Correct | 5 ms | 8532 KB | Output is correct |
| 7 | Correct | 693 ms | 90548 KB | Output is correct |
| 8 | Correct | 1002 ms | 89952 KB | Output is correct |
| 9 | Correct | 1178 ms | 90456 KB | Output is correct |
| 10 | Correct | 586 ms | 90560 KB | Output is correct |
| 11 | Correct | 761 ms | 90464 KB | Output is correct |
| 12 | Correct | 1251 ms | 90492 KB | Output is correct |
| 13 | Incorrect | 5 ms | 8532 KB | Output isn't correct |
| 14 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8532 KB | Output is correct |
| 2 | Correct | 6 ms | 8788 KB | Output is correct |
| 3 | Correct | 4 ms | 8532 KB | Output is correct |
| 4 | Correct | 4 ms | 8532 KB | Output is correct |
| 5 | Correct | 504 ms | 90584 KB | Output is correct |
| 6 | Correct | 5 ms | 8532 KB | Output is correct |
| 7 | Correct | 693 ms | 90548 KB | Output is correct |
| 8 | Correct | 1002 ms | 89952 KB | Output is correct |
| 9 | Correct | 1178 ms | 90456 KB | Output is correct |
| 10 | Correct | 586 ms | 90560 KB | Output is correct |
| 11 | Correct | 761 ms | 90464 KB | Output is correct |
| 12 | Correct | 1251 ms | 90492 KB | Output is correct |
| 13 | Incorrect | 5 ms | 8532 KB | Output isn't correct |
| 14 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8504 KB | Output is correct |
| 2 | Correct | 127 ms | 60720 KB | Output is correct |
| 3 | Correct | 103 ms | 60652 KB | Output is correct |
| 4 | Correct | 85 ms | 60660 KB | Output is correct |
| 5 | Correct | 110 ms | 60756 KB | Output is correct |
| 6 | Incorrect | 93 ms | 60740 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8504 KB | Output is correct |
| 2 | Correct | 127 ms | 60720 KB | Output is correct |
| 3 | Correct | 103 ms | 60652 KB | Output is correct |
| 4 | Correct | 85 ms | 60660 KB | Output is correct |
| 5 | Correct | 110 ms | 60756 KB | Output is correct |
| 6 | Incorrect | 93 ms | 60740 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8504 KB | Output is correct |
| 2 | Correct | 127 ms | 60720 KB | Output is correct |
| 3 | Correct | 103 ms | 60652 KB | Output is correct |
| 4 | Correct | 85 ms | 60660 KB | Output is correct |
| 5 | Correct | 110 ms | 60756 KB | Output is correct |
| 6 | Incorrect | 93 ms | 60740 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8504 KB | Output is correct |
| 2 | Correct | 127 ms | 60720 KB | Output is correct |
| 3 | Correct | 103 ms | 60652 KB | Output is correct |
| 4 | Correct | 85 ms | 60660 KB | Output is correct |
| 5 | Correct | 110 ms | 60756 KB | Output is correct |
| 6 | Incorrect | 93 ms | 60740 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8532 KB | Output is correct |
| 2 | Correct | 6 ms | 8788 KB | Output is correct |
| 3 | Correct | 4 ms | 8532 KB | Output is correct |
| 4 | Correct | 4 ms | 8532 KB | Output is correct |
| 5 | Correct | 504 ms | 90584 KB | Output is correct |
| 6 | Correct | 5 ms | 8532 KB | Output is correct |
| 7 | Correct | 693 ms | 90548 KB | Output is correct |
| 8 | Correct | 1002 ms | 89952 KB | Output is correct |
| 9 | Correct | 1178 ms | 90456 KB | Output is correct |
| 10 | Correct | 586 ms | 90560 KB | Output is correct |
| 11 | Correct | 761 ms | 90464 KB | Output is correct |
| 12 | Correct | 1251 ms | 90492 KB | Output is correct |
| 13 | Incorrect | 5 ms | 8532 KB | Output isn't correct |
| 14 | Halted | 0 ms | 0 KB | - |