제출 #1363571

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

Main

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

const int INF=1e9;

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,0);
    vector<bitset<10001>> possible(m+1);

    for(int i=n-1; i>=0; i--)
    {
        for(int j=0; j<=m; j++)
        {
            possible[j].reset();
        }

        possible[0][0]=1;

        for(int s : contestants[i].scores)
        {
            for(int j=m-1; j>=0; j--)
            {
                possible[j+1] |= (possible[j]<<s);
            }
        }

        int d=0;

        if(i<n-1)
        {
            if(contestants[i].id>contestants[i+1].id)
            {
                d=1;
            }
        }

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

        for(int c=0; c<=m; c++)
        {
            int offset=(m-c)*k;

            for(size_t x=possible[c]._Find_first(); x<=(size_t)mk; x=possible[c]._Find_next(x))
            {
                if((int)x>=d)
                {
                    int r=(int)x+offset;

                    if(r<=mk)
                    {
                        next[r]=min(next[r],dp[x-d]+c);
                    }
                }
            }
        }

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

        dp=next;
    }

    int ans=INF;

    for(int r=0; r<=mk; r++)
    {
        ans=min(ans,dp[r]);
    }

    cout<<ans<<endl;

    return 0;
}

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