Submission #377519

#	Time	Username	Problem	Language	Result	Execution time	Memory
377519		Vimmer	Selotejp (COCI20_selotejp)	C++14	110 / 110	140 ms	8556 KiB

Main

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define N 1001
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

int f[N][(1 << 10)], kol[N][(1 << 10)];

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    int n, m;

    cin >> n >> m;

    string s[n];

    int mask[n];

    for (int i = 0; i < n; i++)
        {
            cin >> s[i];

            mask[i] = 0;
            for (int j = 0; j < m; j++)
                if (s[i][j] == '.')
                    mask[i] |= (1 << j);

            for (int j = 0; j < (1 << m); j++)
            {
                kol[i][j] = 0;

                int p = 0;

                for (int u = 0; u < m; u++)
                {
                    if (s[i][u] == '.' || ((1 << u) & j))
                    {
                        p = 0;

                        continue;
                    }

                    p++;

                    if (p == 1)
                        kol[i][j]++;
                }
            }
        }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j < (1 << m); j++)
            f[i][j] = 1e9;

    f[0][0] = 0;

    for (int i = 0; i < n; i++)
    {
      for (int j = (1 << m) - 1; j >= 0; j--)
        for (int k = 0; k < m; k++)
            if ((1 << k) & j)
                f[i][j ^ (1 << k)] = min(f[i][j ^ (1 << k)], f[i][j]);

      for (int j = 0; j < (1 << m); j++)
        for (int k = 0; k < m; k++)
            {
                if ((1 << k) & j) continue;

                f[i][j ^ (1 << k)] = min(f[i][j ^ (1 << k)], f[i][j] + 1);
            }

      for (int j = 0; j < (1 << m); j++)
      {
          if (__builtin_popcount(j & mask[i]) > 0)
            continue;

          f[i + 1][j] = min(f[i + 1][j], f[i][j] + kol[i][j]);
      }
    }

    int ans = 1e9;

    for (int msk = 0; msk < (1 << m); msk++)
        ans = min(ans, f[n][msk]);

    pri(ans);
}

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