Submission #1363405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363405		liptonek	Monster-Go (EGOI25_monstergo)	C++20	100 / 100	1 ms	344 KiB

Main

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

struct Block 
{
    int n,c,m,k,b;
};

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin>>n;
    
    vector<Block> blocks={{1,12,1,0,12},{2,24,2,1,12},{3,18,3,1,6},{4,16,4,1,4},{5,15,5,1,3},{7,14,7,1,2},{13,13,13,1,1},{6,24,4,2,6},{10,20,5,2,4},{15,18,6,2,3},{28,16,8,2,2},{20,24,6,3,4},{35,21,7,3,3}};
    
    vector<int> dp(n+1,1e9);
    vector<int> p(n+1,-1);

    dp[0]=0;
    
    for(int i=1; i<=n; i++) 
    {
        for(size_t j=0; j<blocks.size(); j++) 
        {
            if(i>=blocks[j].n) 
            {
                if(dp[i-blocks[j].n]+blocks[j].c<dp[i]) 
                {
                    dp[i]=dp[i-blocks[j].n]+blocks[j].c;
                    p[i]=j;
                }
            }
        }
    }
    
    vector<Block> chosen;

    int curr=n;

    while(curr>0) 
    {
        chosen.push_back(blocks[p[curr]]);
    
        curr-=blocks[p[curr]].n;
    }
    
    int current=0;
    
    vector<vector<int>> all;
    
    for(auto& blk : chosen) 
    {
        int m=blk.m;
        int k=blk.k;
        int b=blk.b;
        
        vector<vector<int>> base(m);
    
        for(int i=0; i<m; i++) 
        {
            for(int j=0; j<b; j++) 
            {
                base[i].push_back(current++);
            }
        }
        
        vector<int> keep;

        for(int i=0; i<m-k; i++) 
        {
            keep.push_back(1);
        }

        for(int i=0; i<k; i++) 
        {
            keep.push_back(0);
        }

        sort(keep.begin(),keep.end());
        
        int count=0;
        
        do 
        {
            if(count>=blk.n) 
            {
                break;
            }
        
            vector<int> cur;
            
            for(int i=0; i<m; i++) 
            {
                if(keep[i]) 
                {
                    for(int x : base[i]) 
                    {
                        cur.push_back(x);
                    }
                }
            }

            all.push_back(cur);
            
            count++;
        }while(next_permutation(keep.begin(),keep.end()));
    }
    
    for(auto& lst : all) 
    {
        for(int i=0; i<12; i++) 
        {
            cout<<lst[i]<<(i==11 ? "" : " ");
        }
        
        cout<<endl;
    }
    
    return 0;
}

• Subtask 1: 100 / 100