Submission #575347

#	Time	Username	Problem	Language	Result	Execution time	Memory
575347		web	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	6 ms	2748 KiB

fancyfence

#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

typedef long long ll;

constexpr int mod = 1000000000+7;


int main()
{
    
    int n = 0; cin>>n;
    vector<pair<ll,ll> >sizes(n);
    for(int i  =0; i<n; ++i)
    {
        cin>>sizes[i].first;
    }
    for(int i  =0; i<n; ++i)
    {
        cin>>sizes[i].second;
    }

    vector<bitset<50>> grid(n);
    vector<vector<vector<bitset<50>>>> dp(50,vector<vector<bitset<50>>>(50, vector<bitset<50>>(50)));
    for(int i = 0; i<n; ++i)
    {
        for(int w = 0; w < sizes[i].first; ++w)
        {
            for(int h = 0; h<sizes[i].second; ++h)
            {
                grid[w].set(h);
            }
        }
    }
    ll num = 0; 
  //  cout<<"reach"<<endl;
    for(int startX = 0; startX<50; ++startX)
    {
       // cout<<"start X : "<<startX<<endl;
        for(int startY = 0; startY < 50; ++startY)
        {
         //   cout<<"startY " << startY<<endl;
            if(grid[startX].test(startY))
            {
                num++;
                num%= mod;
                dp[startX][startY][startX].set(startY);
            }
           // cout<<"trivial case "<<endl;
            for(int x = startX; x < 50; ++x)
            {
                for(int y = startY; y <50; ++y)
                {
                   // cout<<"x,y "<<x<<" "<<y<<endl;
                    if(grid[x].test(y))
                    {
                        if(dp[startX][startY][max(startX, x-1)].test(y)
                         && dp[startX][startY][x].test(max(startY, y-1)))
                        {
                            if(startX != x && startY != y)
                            {  
                                num++;
                                num%= mod;
                                dp[startX][startY][x].set(y);
                           }
                        }
                    }
                }
            }
        }
    }
    //cout<<"reach2"<<endl;
    cout<<num<<endl;


    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27