Submission #1248322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248322		escobrand	Selotejp (COCI20_selotejp)	C++20	0 / 110	1 ms	328 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],mn[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;
      mn[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],mn[pre] + __builtin_popcount(mask) + cal(msk ^ mask));
        mn[now] = min(mn[now],dp[mask][now]);
      }
      dp[0][now] = cal(msk) + mn[pre];
      mn[now] = min(mn[now],dp[0][now]);
      // 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<<mn[now];
    
    return 0;
}

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