oj.uz

Submission #536089

# Submission time Handle Problem Language Result Execution time Memory
536089 2022-03-12T10:34:52 Z Killer2501 Selotejp (COCI20_selotejp) C++14
110 / 110
 110 ms 12372 KB 
#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

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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 78 ms 11476 KB Output is correct
3 Correct 14 ms 5972 KB Output is correct
4 Correct 34 ms 8140 KB Output is correct
5 Correct 86 ms 12176 KB Output is correct
6 Correct 86 ms 12268 KB Output is correct
7 Correct 79 ms 12016 KB Output is correct
8 Correct 70 ms 11432 KB Output is correct
9 Correct 77 ms 11476 KB Output is correct
10 Correct 100 ms 12372 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 78 ms 11476 KB Output is correct
3 Correct 14 ms 5972 KB Output is correct
4 Correct 34 ms 8140 KB Output is correct
5 Correct 86 ms 12176 KB Output is correct
6 Correct 86 ms 12268 KB Output is correct
7 Correct 79 ms 12016 KB Output is correct
8 Correct 70 ms 11432 KB Output is correct
9 Correct 77 ms 11476 KB Output is correct
10 Correct 100 ms 12372 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 572 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 576 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 3 ms 4564 KB Output is correct
20 Correct 16 ms 6356 KB Output is correct
21 Correct 37 ms 8364 KB Output is correct
22 Correct 76 ms 12080 KB Output is correct
23 Correct 73 ms 12124 KB Output is correct
24 Correct 76 ms 11932 KB Output is correct
25 Correct 90 ms 12144 KB Output is correct
26 Correct 98 ms 11676 KB Output is correct
27 Correct 110 ms 11764 KB Output is correct
28 Correct 110 ms 12132 KB Output is correct