Submission #1333879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333879		yusifm	Colouring a rectangle (eJOI19_colouring)	C++20	0 / 100	68 ms	14988 KiB

colouring

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
const int sz=1000000,INF=1000000000;
using namespace std;
vector<ll>pow2;
bool f(ll num1,ll num2,set<pair<ll,ll>>nums)
{
    for(int i=0;i<num1;i++)
    {
        for(int j=0;j<num2;j++)
        {
            if(nums.find({i,j})==nums.end())
            {
                return false;
            }
        }
    }
    return true;
}
void solve()
{
    ll n,m,num1,num2,idx1,idx2,res,ans=INF;
    cin>>m>>n;
    vector<ll>nums1,nums2,nums;
    set<pair<ll,ll>>Res;
    for(int i=0;i<n+m-1;i++)
    {
        cin>>num1;
        nums1.pb(num1);
    }
    for(int i=0;i<n+m-1;i++)
    {
        cin>>num2;
        nums2.pb(num2);
    }
    for(int i=0;i<nums2.size();i++)
    {
        nums.pb(nums2[i]);
    }
    for(int i=0;i<nums1.size();i++)
    {
        nums.pb(nums1[i]);
    }
    for(int i=1;i<pow2[nums.size()];i++)
    {
        Res.clear(),res=0;
        for(ll j=0;j<nums.size();j++)
        {
            if(i&pow2[j])
            {
                res+=nums[j];
                if(j<n+m-1)
                {
                    if(j==0)
                    {
                        Res.in({0,0});
                    }
                    else if(j==n+m-2)
                    {
                        Res.in({n-1,m-1});
                    }
                    else
                    {
                        if(j<n)
                        {
                            idx1=min(j,n-1),idx2=j-idx1;
                            while(idx1>=0 && idx2<=m-1)
                            {
                                Res.in({idx1,idx2}),idx1--,idx2++;
                            }
                        }
                        else
                        {
                            idx1=n-1,idx2=j-n+1;
                            while(idx1>=0 && idx2<=m-1)
                            {
                                Res.in({idx1,idx2}),idx1--,idx2++;
                            }
                        }
                    }
                }
                else
                {
                    if(j==n+m-1)
                    {
                        Res.in({n-1,0});
                    }
                    else if(j==2*(n+m-1)-1)
                    {
                        Res.in({0,m-1});
                    }
                    else
                    {
                        if(j-(n+m-1)<n)
                        {
                            idx1=n-(j-(n+m-1))-1,idx2=0;
                            while(idx1<=n-1 && idx2<=m-1)
                            {
                                Res.in({idx1,idx2}),idx1++,idx2++;
                            }
                        }
                        else
                        {
                            idx1=0,idx2=j-(n+m-1)-n+1;
                            while(idx1<=n-1 && idx2<=m-1)
                            {
                                Res.in({idx1,idx2}),idx1++,idx2++;
                            }
                        }
                    }
                }
            }
        }
        if(f(n,m,Res))
        {
            ans=min(ans,res);
        }
    }
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    for(int i=1;i<INF;i*=2)
    {
        pow2.pb(i);
    }
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20