제출 #1166853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166853		PoonYaPat	Council (JOI23_council)	C++20	78 / 100	4082 ms	38384 KiB

council

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

const int A=10;
int n,m,mmin[1<<A][1<<A][2],a[1<<A][1<<A],c[300001][20],bit[1<<A],sum[20],val[300001],power[20];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int i=0; i<(1<<A); ++i) bit[i]=__builtin_popcount(i);
    memset(mmin,0x3f,sizeof(mmin));
    power[0]=1;
    for (int i=1; i<20; ++i) power[i]=2*power[i-1];

    cin>>n>>m;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            cin>>c[i][j];
            sum[j]+=c[i][j];
            val[i]+=c[i][j]*power[j];
        }
    }

    for (int i=0; i<n; ++i) {
        int left = val[i]&((1<<A)-1);
        int right = val[i]>>A;

        for (int mask=0; mask<(1<<A); ++mask) {
            if (bit[left&mask]<=mmin[mask][right][0]) {
                mmin[mask][right][1]=mmin[mask][right][0];
                mmin[mask][right][0]=bit[left&mask];
                a[mask][right]=i;
            } else if (bit[left&mask]<mmin[mask][right][1]) mmin[mask][right][1]=bit[left&mask];
        }
    }

    for (int i=0; i<n; ++i) {
        int temp=0,ans=0,cnt=0;
        for (int j=0; j<m; ++j) {
            if (sum[j]-c[i][j]>=n/2) ++cnt;
            if (sum[j]-c[i][j]==n/2) temp+=power[j];
        }

        int left = temp&((1<<A)-1);
        int right = temp>>A;

        for (int mask=0; mask<(1<<A); ++mask) {
            if (a[left][mask]==i) ans=max(ans,cnt-(bit[right&mask]+mmin[left][mask][1]));
            else ans=max(ans,cnt-(bit[right&mask]+mmin[left][mask][0]));
        }

        cout<<ans<<"\n";
    }
}

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