제출 #1077631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077631		vjudge1	Council (JOI23_council)	C++98	56 / 100	4075 ms	21692 KiB

council

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=2e6+10;
const ll inf=2e18+10;
const ll mod=1e9+7;
ll n,m,a[M],cnt[M],cntb[40],ans[M];
int main() {
  ios_base::sync_with_stdio(0),cin.tie(0);
  cin>>n>>m;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++) {
      ll x;
      cin>>x;
      a[i]+=(x*(1<<j));
      cntb[j]+=x;
    }
  for(int i=0;i<n;i++) {
    for(int j=a[i];j<(1<<m);j++,j|=a[i]) {
      cnt[j]++;
    }
  }
  for(int i=0;i<(1<<m);i++)
    ans[i]=-1;
  for(int i=0;i<n;i++) {
    ll res=0,x=0;
    for(int j=0;j<m;j++) {
      if(cntb[j]-bool(((1<<j)&a[i])>0)>n/2)
        res++;
      else if(cntb[j]-bool(((1<<j)&a[i])>0)==n/2) {
        x+=(1<<j);
      }
    }
    if(ans[x]>-1) {
      cout<<ans[x]<<'\n';
      continue;
    }
    ll res1=0;
    for(int j=x;j>=0;j--) {
      if(j<0)
        break;
      j&=x;
      ll y=j+(((1<<m)-1)^x);
      if((a[i]&y)==a[i])
        cnt[y]--;
      if(cnt[y]>0)
        res1=max(res1,(ll)__builtin_popcountll(x)-__builtin_popcountll(j));
      if((a[i]&y)==a[i])
        cnt[y]++;
    }
    ans[x]=res1+res;
    cout<<res1+res<<'\n';
  }
}

• 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