제출 #1363447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363447		liptonek	IMO (EGOI25_imo)	C++20	54 / 100	6095 ms	9584 KiB

Main

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

const int MAX_MK=10001;
const int INF=1e9;

static bitset<MAX_MK> can[101];
static int S[101][MAX_MK];

struct Contestant
{
    int id;
    int total;

    vector<int> scores;
};

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

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

    vector<Contestant> contestants(n);

    for(int i=0; i<n; i++)
    {
        contestants[i].id=i;
        contestants[i].total=0;
        contestants[i].scores.resize(m);

        for(int j=0; j<m; j++)
        {
            cin>>contestants[i].scores[j];

            contestants[i].total+=contestants[i].scores[j];
        }
    }

    sort(contestants.begin(),contestants.end(), [](const Contestant& a, const Contestant& b)
    {
        if(a.total!=b.total)
        {
            return a.total>b.total;
        }

        return a.id<b.id;
    });

    int mk=m*k;

    vector<int> dp(mk+1,INF);

    for(int i=n-1; i>=0; i--)
    {
        const auto& c=contestants[i];

        for(int r=0; r<=m; r++)
        {
            can[r].reset();
        }

        can[0][0]=1;

        for(int s : c.scores)
        {
            for(int r=m-1; r>=0; r--)
            {
                can[r+1] |= (can[r]<<s);
            }
        }

        for(int r=0; r<=m; r++)
        {
            int last=-1;

            for(int s=0; s<=mk; s++)
            {
                if(can[r][s])
                {
                    last=s;
                }

                S[r][s]=last;
            }
        }

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

        int offset=(i==n-1) ? 0 : (contestants[i].id>contestants[i+1].id ? 1 : 0);

        for(int r=0; r<=m; r++)
        {
            int base=(m-r)*k;

            for(int v=base; v<=mk; v++)
            {
                int xx=S[r][v-base];

                if(xx==-1)
                {
                    continue;
                }

                int u=xx-offset;
                int cost;

                if(i==n-1)
                {
                    if(u>=0)
                    {
                        cost=r;
                    }
                    else
                    {
                        continue;
                    }
                }
                else
                {
                    if(u<0)
                    {
                        continue;
                    }

                    int prev=dp[min(u,mk)];

                    if(prev==INF)
                    {
                        continue;
                    }

                    cost=r+prev;
                }

                if(cost<next[v])
                {
                    next[v]=cost;
                }
            }
        }

        for(int v=1; v<=mk; v++)
        {
            if(next[v-1]<next[v])
            {
                next[v]=next[v-1];
            }
        }

        dp=next;
    }

    cout<<dp[mk]<<endl;

    return 0;
}

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