Submission #1248320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248320		escobrand	Selotejp (COCI20_selotejp)	C++20	110 / 110	532 ms	448 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb emplace_back
#define ll long long 
#define fi first
#define se second
int t,n,i,m,msk,mask,sub;
const int inf = 1e6;
const int lg = 10;
string s;
int dp[1<<lg][2];
bool now,pre;

int cal(int mask)
{
  bool c = 0;
  int ans = 0;
  while(mask)
  {
    if(c != (mask & 1))
    {
      ans += c = (mask & 1);
    }
    mask>>=1;
  }
  return ans;
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    
    for(mask = 1;mask<(1<<m);mask++)dp[mask][0] = inf;
    while(n--)
    {
      now = !now;
      pre = !now;
      cin>>s;
      msk = bitset<10>(s,0,m,'.','#').to_ulong();
      for(mask = 0;mask<(1<<m);mask++)dp[mask][now] = inf;
      for(mask = msk;mask;mask = (mask - 1) & msk)
      {
        for(sub = mask;sub;sub =(sub - 1)&mask)
        {
          dp[mask][now] = min(dp[mask][now],dp[sub][pre] + __builtin_popcount(mask ^ sub) + cal(msk ^ mask));
        }
        dp[mask][now] = min(dp[mask][now],dp[0][pre] + __builtin_popcount(mask) + cal(msk ^ mask));
      }
      dp[0][now] = cal(msk) + dp[0][pre];
      for(i = 0;i<m;i++)
      {
        for(mask = 0;mask<(1<<m);mask++)
        {
          if((mask >> i & 1)==0)
          {
            dp[mask][now] = min(dp[mask][now],dp[mask ^ (1<<i)][now]);
          }
        }
      }
    }
    cout<<dp[0][now];
    
    return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40