Submission #536089

#	Time	Username	Problem	Language	Result	Execution time	Memory
536089		Killer2501	Selotejp (COCI20_selotejp)	C++14	110 / 110	110 ms	12372 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e3+2;
const int M = 52;
const int mod = 998244353;
const ll base = 75;
const ll inf = 1e16;
ll n, lab[N], t, c[N], m, k, a[N], b[N], d[N], dp[N][N];
ll ans, tong;
string s[N];
vector<pii> adj[N];
vector<int> vi, cur;
bool vis[N];
int r, sz;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n&1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
void add(int& x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
}
int findp(int u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
bool hop(int u, int v)
{
    u = findp(u);
    v = findp(v);
    if(u == v)return false;
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
}
struct BIT
{
    int n;
    vector<ll> fe;
    BIT(){}
    void init(int _n)
    {
        n = _n;
        fe.resize(n+1, 0);
    }
    void reset()
    {
        fill(fe.begin(), fe.end(), 0);
    }
    void add(int id, int x)
    {
        if(id <= 0)exit(0);
        for(; id <= n; id += id & -id)fe[id] += x;
    }
    ll get(int id)
    {
        ll total = 0;
        id = min(id, n);
        if(id <= 0)return total;
        for(; id; id -= id & -id)total += fe[id];
        return total;
    }
}bit;

pii p[N];
ll C(int u, int v)
{
    if(u > v)return 0;
    return  a[v] * b[u] % mod * b[v-u] % mod;
}
void add(ll& x, ll y)
{
    x += y;
    if(x >= mod)x -= mod;
}
void sol()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)cin >> s[i];
    for(int i = 1; i < (1<<m); i ++)dp[0][i] = inf;
    for(int i = 0; i < n; i ++)
    {
        for(int mask = 0; mask < (1<<m); mask ++)
        {
            dp[i+1][mask] = inf;
            for(int j = 0; j < m; j ++)
            {
                if(mask >> j & 1)dp[i][mask] = min(dp[i][mask], dp[i][mask^(1<<j)]+1);
            }
        }
        for(int mask = (1<<m)-1; mask >= 0; mask --)
        {
            for(int j = 0; j < m; j ++)
            {
                if(mask >> j & 1)continue;
                dp[i][mask] = min(dp[i][mask], dp[i][mask^(1<<j)]);
            }
        }
        for(int mask = 0; mask < (1<<m); mask ++)
        {
            if(dp[i][mask] == inf)continue;
            //cout << i <<" "<<mask<<" "<<dp[i][mask]<<'\n';
            tong = dp[i][mask];
            bool ok = false;
            for(int j = 0; j < m; j ++)
            {
                if(mask >> j & 1)
                {
                    if(s[i][j] == '.')
                    {
                        tong = inf;
                        break;
                    }
                    ok = false;
                    continue;
                }
                if(s[i][j] == '#')
                {
                    if(!ok)++tong;
                    ok = true;
                }
                else ok = false;
            }
            dp[i+1][mask] = min(dp[i+1][mask], tong);
        }
    }
    ans = inf;
    for(int i = 0; i < (1<<m); i ++)ans = min(ans, dp[n][i]);
    cout << ans;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
1234
21
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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