oj.uz

Submission #377599

# Submission time Handle Problem Language Result Execution time Memory
377599 2021-03-14T11:09:28 Z nguyen31hoang08minh2003 Selotejp (COCI20_selotejp) C++14
70 / 110
 1000 ms 8940 KB 
#include <bits/stdc++.h>
#define fore(i, a, b) for (ll i = (a), _b = (b); i < (_b); i++)
#define fort(i, a, b) for (ll i = (a), _b = (b); i <= (_b); i++)
#define ford(i, a, b) for (ll i = (a), _b = (b); i >= (_b); i--)
#define fi first
#define se second
#define sz(x) ((ll)(x).size())
#define getbit(x, i) ((x) & (1LL << (i)))
#define on(x, i) ((x) | (1LL << (i)))
#define off(x, i) ((x) ^ (1LL << (i)))
#define lowbit(x) ((x) & (-(x)))
#define pb push_back
#define pf push_front
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

bool mini(ll &a, const ll b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

bool maxi(ll &a, const ll b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll maxM = 1005;
const ll inf = 1e18;
const ll maxN = 10;

ll m, n, full, choco[maxM];
ll cntbit[1LL << maxN], row[1LL << maxN], dp[maxM][1LL << maxN];
vi submsk[1LL << maxN];
bool vis[maxM][1LL << maxN];
char c[maxM][maxN];

ll CountBit(ll x) {
    ll res = 0;
    for (; x > 0; x -= lowbit(x))
        res++;
    return res;
}

ll costRow(ll msk) {
    ll res = 0;
    vi row;
    row.pb(0);
    fore(i, 0 , n)
        row.pb((bool)getbit(msk, i));
    fore(i, 1, sz(row))
        if (row[i] == 1 && !row[i - 1])
            res++;
    return res;
}

ll DP(ll i, ll prv) {
    if (i > m)
        return 0;
    if (!vis[i][prv]) {
        vis[i][prv] = true;
        dp[i][prv] = inf;
//        fort(cols, 0, full)
//            if ((choco[i] & cols) == cols) {
//                mini(dp[i][prv], cntbit[cols] - cntbit[cols & prv] + row[choco[i] ^ cols] + DP(i + 1, cols & choco[i + 1]));
//            }
        ll cols;
        for (vi::iterator j = submsk[choco[i]].begin(); j != submsk[choco[i]].end(); j++) {
            cols = *j;
            mini(dp[i][prv], cntbit[cols] - cntbit[cols & prv] + row[choco[i] ^ cols] + DP(i + 1, cols));
        }
    }
    return dp[i][prv];
}

void input() {
    cin >> m >> n;
    fort(i, 1, m) {
        cin >> c[i];
        fore(j, 0, n)
            if (c[i][j] == '#')
                choco[i] |= (1LL << j);
    }
}

void solve() {
    //preprocess
    full = (1LL << n) - 1;
    fort(i, 0, full) {
        row[i] = costRow(i);
        cntbit[i] = CountBit(i);
        fort(j, 0, full)
            if ((i & j) == j)
                submsk[i].pb(j);
    }
    //main solve
    cout << DP(1, 0) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
    return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 8 ms 6508 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 6 ms 5612 KB Output is correct
5 Correct 10 ms 7276 KB Output is correct
6 Correct 11 ms 7660 KB Output is correct
7 Correct 10 ms 7660 KB Output is correct
8 Correct 6 ms 6124 KB Output is correct
9 Correct 7 ms 6892 KB Output is correct
10 Correct 16 ms 8044 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 4 ms 1004 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 9 ms 1004 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 4 ms 908 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 8 ms 6508 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 6 ms 5612 KB Output is correct
5 Correct 10 ms 7276 KB Output is correct
6 Correct 11 ms 7660 KB Output is correct
7 Correct 10 ms 7660 KB Output is correct
8 Correct 6 ms 6124 KB Output is correct
9 Correct 7 ms 6892 KB Output is correct
10 Correct 16 ms 8044 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 4 ms 1004 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 9 ms 1004 KB Output is correct
15 Correct 2 ms 876 KB Output is correct
16 Correct 2 ms 1004 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 4 ms 908 KB Output is correct
19 Correct 4 ms 5356 KB Output is correct
20 Correct 8 ms 5484 KB Output is correct
21 Correct 14 ms 6124 KB Output is correct
22 Correct 5 ms 5868 KB Output is correct
23 Correct 5 ms 6252 KB Output is correct
24 Correct 8 ms 6764 KB Output is correct
25 Correct 35 ms 8044 KB Output is correct
26 Correct 509 ms 8940 KB Output is correct
27 Execution timed out 1095 ms 7276 KB Time limit exceeded
28 Halted 0 ms 0 KB -