제출 #1363594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363594		liptonek	IMO (EGOI25_imo)	C++20	59 / 100	6094 ms	9412 KiB

Main

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

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

inline int find(const unsigned long long* bv, int start, int xw) 
{
    int w=start>>6;

    if(w>xw) 
    {
        return -1;
    }

    int bit=start & 63;
    unsigned long long mask=bv[w]>>bit;
    
    if(mask>0) 
    {
        return(w<<6)+bit+__builtin_ctzll(mask);
    }
    
    for(int i=w+1; i<=xw; i++) 
    {
        if(bv[i]>0) 
        {
            return(i<<6)+__builtin_ctzll(bv[i]);
        }
    }

    return -1;
}

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,0);
    vector<int> next(xm+1,INF);
    vector<int> lower(xm+1,-1);

    unsigned long long b[101][WORDS];
    int xw[101];

    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;

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

        vector<int> sorted=a[u];
        
        sort(sorted.begin(),sorted.end()); 

        for(int j=0; j<m; j++) 
        {
            int x=sorted[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);
                    
                        unsigned long long* dst=b[v];
                    
                        const unsigned long long* src=b[v-1];
                    
                        for(int w=0; w<=mw; w++) 
                        {
                            dst[w] |= src[w];
                        }
                    }
                }

                continue;
            }
            
            int sw=x/64;
            int sb=x%64;
            
            if(sb==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+sw);
                    
                        unsigned long long* dst=b[v]+sw;
                    
                        const unsigned long long* src=b[v-1];
                    
                        for(int w=0; w<=mw; w++) 
                        {
                            dst[w] |= src[w];
                        }
                    }
                }
            } 
            else 
            {
                int right=64-sb;
            
                for(int v=j+1; v>=1; v--) 
                {
                    if(xw[v-1]!=-1) 
                    {
                        int mw=xw[v-1];
                    
                        xw[v]=max(xw[v],mw+sw+1);
                    
                        unsigned long long* dst1=b[v]+sw;
                        unsigned long long* dst2=b[v]+sw+1;
                    
                        const unsigned long long* src=b[v-1];
                    
                        for(int w=0; w<=mw; w++) 
                        {
                            dst1[w] |= (src[w]<<sb);
                            dst2[w] |= (src[w]>>right);
                        }
                    }
                }
            }
        }

        int last=-1;

        for(int req=xm; req>=0; req--) 
        {
            if(req<xm && dp[req]>dp[req+1]) 
            {
                last=req+1;
            }
            
            lower[req]=last;
        }

        int first=0;
        
        while(first<=xm && dp[first]==INF) 
        {
            first++;
        }

        fill(next.begin(),next.end(),INF);

        if(first<=xm) 
        {
            for(int v=0; v<=m; v++) 
            {
                if(xw[v]==-1) 
                {
                    continue;
                }
                
                int current=first;
                
                while(current<=xm) 
                {
                    int search=current+d;
                
                    if(search>xm) 
                    {
                        break;
                    }
                    
                    int r=find(b[v],search,xw[v]);
                    
                    if(r==-1) 
                    {
                        break;
                    }
                    
                    int cost=v+dp[r-d];
                    int xval=r+(m-v)*k;
                    
                    if(xval<=xm) 
                    {
                        next[xval]=min(next[xval],cost);
                    }
                    
                    int nreq=lower[r-d];
                    
                    if(nreq==-1) 
                    {
                        break;
                    }
                    
                    current=nreq;
                }
            }
        }

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

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

• 서브태스크 0: 0 / 0
• 서브태스크 1: 10 / 10
• 서브태스크 2: 0 / 13
• 서브태스크 3: 10 / 10
• 서브태스크 4: 18 / 18
• 서브태스크 5: 21 / 21
• 서브태스크 6: 0 / 28