Submission #1363585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363585		liptonek	IMO (EGOI25_imo)	C++20	72 / 100	6095 ms	9412 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int WORDS=160;

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

    int n,m,k;
    cin>>n>>m>>k;

    vector<vector<int>> a(n,vector<int>(m));
    vector<pair<int,int>> scores(n);

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

        scores[i]={-sum,i};
    }

    sort(scores.begin(),scores.end());

    vector<int> p(n);

    for(int i=0; i<n; i++) 
    {
        p[i]=scores[i].second;
    }

    int xm=m*k;
    
    vector<int> dp(xm+1,INF);

    for(int i=n-1; i>=0; i--) 
    {
        int u=p[i];
        int nu=(i<n-1) ? p[i+1] : -1;
        int d=(i<n-1) ? ((u>nu) ? 1 : 0) : 0;

        unsigned long long b[101][WORDS];

        memset(b,0,sizeof(b));

        int xw[101];

        for(int v=0; v<=m; v++) 
        {
            xw[v]=-1;
        }

        b[0][0]=1;
        xw[0]=0;

        for(int j=0; j<m; j++) 
        {
            int x=a[u][j];
        
            if(x==0) 
            {
                for(int v=j+1; v>=1; v--) 
                {
                    if(xw[v-1]!=-1) 
                    {
                        int mw=xw[v-1];
                    
                        xw[v]=max(xw[v],mw);
                    
                        for(int w=0; w<=mw; w++) 
                        {
                            b[v][w] |= b[v-1][w];
                        }
                    }
                }

                continue;
            }
            
            int sw=x/64;
            int sb=x%64;

            for(int v=j+1; v>=1; v--) 
            {
                if(xw[v-1]!=-1) 
                {
                    int mw=xw[v-1];
                
                    if(sb==0) 
                    {
                        for(int w=mw; w>=0; w--) 
                        {
                            b[v][w+sw] |= b[v-1][w];
                        }
                        
                        xw[v]=max(xw[v],mw+sw);
                    } 
                    else 
                    {
                        for(int w=mw; w>=0; w--) 
                        {
                            b[v][w+sw+1] |= (b[v-1][w]>>(64-sb));
                            b[v][w+sw] |= (b[v-1][w]<<sb);
                        }
                        
                        xw[v]=max(xw[v],mw+sw+1);
                    }
                }
            }
        }

        vector<int> next(xm+1,INF);

        if(i==n-1) 
        {
            for(int v=0; v<=m; v++) 
            {
                int mw=xw[v];
            
                if(mw==-1) 
                {
                    continue;
                }
            
                for(int w=0; w<=mw; w++) 
                {
                    unsigned long long mask=b[v][w];
                
                    while(mask>0) 
                    {
                        int bit=__builtin_ctzll(mask);
                        int r=w*64+bit;
                    
                        mask &= mask-1; 
                        
                        int val=r+(m-v)*k;

                        if(val<=xm) 
                        {
                            next[val]=min(next[val],v);
                        }
                    }
                }
            }
        } 
        else 
        {
            for(int v=0; v<=m; v++) 
            {
                int mw=xw[v];
            
                if(mw==-1) 
                {
                    continue;
                }
            
                for(int w=0; w<=mw; w++) 
                {
                    unsigned long long mask=b[v][w];
                
                    while(mask>0) 
                    {
                        int bit=__builtin_ctzll(mask);
                        int r=w*64+bit;
                    
                        mask &= mask-1;
                        
                        int req=r-d;
                    
                        if(req>=0) 
                        {
                            req=min(req,xm);
                        
                            if(dp[req]!=INF) 
                            {
                                int val=r+(m-v)*k;
                            
                                if(val<=xm) 
                                {
                                    next[val]=min(next[val],v+dp[req]);
                                }
                            }
                        }
                    }
                }
            }
        }

        for(int mval=1; mval<=xm; mval++) 
        {
            next[mval]=min(next[mval],next[mval-1]);
        }
        
        dp=next;
    }

    cout<<dp[xm]<<endl;
    
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 28