Submission #1147574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147574		fryingduc	Council (JOI23_council)	C++20	56 / 100	4096 ms	16172 KiB

council

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
const int MASK = (1 << 20) + 5;
const int HALF = 1024;
int n, m;
bool b[maxn][21];
int a[maxn], cnt[21];
bool unused[21];
int maxr[maxn], tight[maxn];
int f[HALF][HALF];
int res[maxn];
int half, other;

void upd(int c) {
  int fmask = c % (1 << half);
  int smask = c >> half;
  
  for (int mask = 0; mask < (1 << half); ++mask) {
    int cnt = 0;
    for (int i = 0; i < half; ++i) {
      if (mask >> i & 1 and fmask >> i & 1) {
        ++cnt;
      }
    }
    f[smask][mask] = min(f[smask][mask], cnt);
  }
}

int get(int c) {
  int fmask = c % (1 << half);
  int smask = c >> half;
  int xx = m;
  for (int mask = 0; mask < (1 << other); ++mask) {
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
      if (mask >> i & 1 and smask >> i & 1) {
        ++cnt;
      }
    }
    xx = min(xx, cnt + f[mask][fmask]);
  }
  return xx;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> b[i][j];
    }
  }
  int add = 0;
  for (int i = 0; i < m; ++i) {
    int sum = 0;
    for (int j = 1; j <= n; ++j) {
      sum += b[j][i];
    }
    if (sum - 2 >= n / 2) {
      ++add;
      unused[i] = 1;
    } else if (sum < n / 2) {
      unused[i] = 1;
    }
  }
  int new_m = 0;
  for (int j = 0; j < m; ++j) {
    if (unused[j]) continue;
    for (int i = 1; i <= n; ++i) {
      if (b[i][j]) {
        a[i] |= (1 << new_m);
        ++cnt[new_m];
      }
    }
    ++new_m;
  }
  m = new_m;
  memset(f, 0x3f, sizeof(f));
  half = m / 2, other = m - half;
  for (int i = 1; i <= n; ++i) {
    int max_res = 0;
    for (int j = 0; j < m; ++j) {
      cnt[j] -= (a[i] >> j & 1);
    }
    int mask = 0;
    for (int j = 0; j < m; ++j) {
      if (cnt[j] >= n / 2) {
        ++max_res;
        if ((cnt[j] - 1) < n / 2) {
          mask |= (1 << j);
        }
      }
    }
    maxr[i] = max_res;
    tight[i] = mask;
    res[i] = max(res[i], maxr[i] - get(mask));
    upd(a[i]);
    for (int j = 0; j < m; ++j) {
      cnt[j] += (a[i] >> j & 1);
    }
  }
  memset(f, 0x3f, sizeof(f));
  for (int i = n; i; --i) {
    res[i] = max(res[i], maxr[i] - get(tight[i]));
    upd(a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    cout << res[i] + add << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
3 4
0 0 0 0 
0 1 1 0
1 0 0 1
*/

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22