Submission #925990

#	Time	Username	Problem	Language	Result	Execution time	Memory
925990		andrei_boaca	Council (JOI23_council)	C++17	100 / 100	633 ms	56016 KiB

council

#include <bits/stdc++.h>

using namespace std;
int n,m,v[300005][25],me[300005],have[(1<<20)+1],sol[(1<<20)+1];
int suma[25],dp[(1<<20)+1];
bool isover(int a,int b)
{
    return a>=b&&(a^b)==(a-b);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int mask=0;
        for(int j=1;j<=m;j++)
        {
            cin>>v[i][j];
            mask=(mask*2+v[i][j]);
            suma[j]+=v[i][j];
        }
        me[i]=mask;
        have[mask]=1;
        dp[mask]++;
    }
    for(int bit=0;bit<m;bit++)
        for(int mask=0;mask<(1<<m);mask++)
            if((mask>>bit)&1)
                dp[mask]=dp[mask]+dp[mask^(1<<bit)];
    for(int mask=0;mask<(1<<m);mask++)
        if(have[mask])
        {
            int need=0,can=0;
            for(int i=m-1;i>=0;i--)
            {
                need*=2;
                int val=((mask>>i)&1);
                int poz=m-i;
                int s=suma[poz]-val;
                if(s-1>=n/2)
                {
                    sol[mask]++;
                    need++;
                }
                if(s<n/2)
                    need++;
                if(s==n/2)
                {
                    need+=0;
                    can++;
                }
            }
            int best=0;
            for(int overmask=need;overmask<(1<<m);overmask=(overmask+1)|need)
                if(dp[overmask]-isover(overmask,mask)>0)
                {
                    int nr=__builtin_popcount(overmask-need);
                    nr=can-nr;
                    best=max(best,nr);
                    if(best==can)
                        break;
                }
            sol[mask]+=best;
        }
    for(int i=1;i<=n;i++)
        cout<<sol[me[i]]<<'\n';
    return 0;
}

• 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: 22 / 22