oj.uz

Submission #212313

# Submission time Handle Problem Language Result Execution time Memory
212313 2020-03-22T17:06:16 Z model_code Skandi (COCI20_skandi) C++17
50 / 110
 2693 ms 262064 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxm = 10;
const int maxn = 505;
const int inf = 1e9;
int max_mask;
int N, M;
int dp[maxn][(1 << maxm)];
int prijelaz[maxn][(1 << maxm)];
int space[maxn][maxm];
int sol = inf;
int mask_sol;
vector <int> v[maxn][(1 << maxm)];
string s[maxn];

int get_val(int x, int line)
{
    int val = 0;
        for (int k = 1; k <= M; k++)
            if (s[line][k] == '0')
                val += ((1 << (k - 1)) & x);
    return val;
}

int get_plus(int x, int line)
{
    int plus = 0;
    for (int k = 1; k < M; k++)
         if (s[line][k] == '1')
             if (((1 << (k - 1)) & x) == (1 << (k - 1)))
                plus++;
    return plus;
}

void input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> s[i];
}

void solve()
{
    max_mask = (1 << (M - 1));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < max_mask; j++)
            dp[i][j] = prijelaz[i][j] = inf;
    for (int i = 0; i < max_mask; i++)
        dp[0][i] = __builtin_popcount(i);
    for (int i = 1; i < N; i++)
    {
        int cnt = -1;
        for (int j = M - 1; j >= 0; j--)
        {
            cnt++;
            if (s[i][j] == '1') {space[i][j] = cnt; cnt = -1;}
        }
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (s[i][j] == '1')
            {
                int control = 0;
                for (int k = j + 1; k <= j + space[i][j]; k++)
                    control |= (1 << (k - 1));
                for (int k = 0; k < max_mask; k++)
                    if ((k & control) != control)
                        {dp[i - 1][k]++; v[i - 1][k].push_back(j + 1);}
            }
        }
        for (int j = 0; j < max_mask; j++)
        {
            int val = get_val(j, i);
            prijelaz[i][val] = min(prijelaz[i][val], dp[i - 1][j]);
        }

        for (int j = 0; j < max_mask; j++)
        {
            int val = get_val(j, i);
            dp[i][j] = prijelaz[i][val] + get_plus(j, i);
        }
    }

    for (int i = 0; i < max_mask; i++)
    {
        if (dp[N - 1][i] < sol)
        {
            sol = dp[N - 1][i];
            mask_sol = i;
        }
    }

    cout << sol << '\n';
}

void reconstruct()
{
    int last_mask_sol = mask_sol;
    int line = N - 1;
    int minx = 1e9;
    int const_val;

    while (line >= 0)
    {
        for (int i = 1; i < M; i++)
        {
            if (s[line][i] == '1')
                if ((mask_sol & (1 << (i - 1))) == (1 << (i - 1)))
                    cout << line + 1 << ' ' << i + 1 << " DOLJE\n";
        }
        for (int i = 0; i < v[line][mask_sol].size(); i++)
            cout << line + 2 << ' ' << v[line][mask_sol][i] << " DESNO\n";

        if (line > 0)
        {
            const_val = get_val(mask_sol, line);
            last_mask_sol = mask_sol;
            minx = 1e9;

            for (int i = 0; i < max_mask; i++)
            {
                if (get_val(i, line) == const_val)
                    if (dp[line - 1][i] < minx)
                        {minx = dp[line - 1][i]; mask_sol = i;}
            }
        }

        line--;
    }

    return;
}

int main()
{
    input();
    solve();
    reconstruct();
}

Compilation message

skandi.cpp: In function 'void reconstruct()':
skandi.cpp:114:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v[line][mask_sol].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skandi.cpp:101:9: warning: variable 'last_mask_sol' set but not used [-Wunused-but-set-variable]
     int last_mask_sol = mask_sol;
         ^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12544 KB Correct.
2 Correct 11 ms 12544 KB Correct.
3 Correct 12 ms 12544 KB Correct.
4 Correct 13 ms 12544 KB Correct.
5 Correct 14 ms 12544 KB Correct.
6 Correct 13 ms 12544 KB Correct.
7 Correct 12 ms 12520 KB Correct.
8 Correct 12 ms 12544 KB Correct.
9 Correct 12 ms 12544 KB Correct.
10 Correct 12 ms 12544 KB Correct.
11 Correct 12 ms 12520 KB Correct.
12 Correct 11 ms 12520 KB Correct.
13 Correct 12 ms 12592 KB Correct.
14 Correct 11 ms 12596 KB Correct.
15 Correct 11 ms 12544 KB Correct.
16 Correct 13 ms 12576 KB Correct.
17 Correct 15 ms 12576 KB Correct.
18 Correct 14 ms 12544 KB Correct.
19 Correct 13 ms 12544 KB Correct.
20 Correct 14 ms 12544 KB Correct.
21 Correct 12 ms 12544 KB Correct.
22 Correct 12 ms 12520 KB Correct.
23 Correct 14 ms 12464 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15976 KB Correct.
2 Correct 12 ms 14080 KB Correct.
3 Correct 13 ms 15360 KB Correct.
4 Correct 12 ms 13952 KB Correct.
5 Correct 15 ms 13952 KB Correct.
6 Correct 13 ms 13440 KB Correct.
7 Correct 13 ms 13416 KB Correct.
8 Correct 20 ms 15232 KB Correct.
9 Correct 46 ms 24440 KB Correct.
10 Correct 47 ms 23620 KB Correct.
11 Correct 54 ms 23880 KB Correct.
12 Correct 60 ms 24288 KB Correct.
13 Correct 48 ms 23800 KB Correct.
14 Correct 53 ms 24048 KB Correct.
15 Correct 68 ms 24312 KB Correct.
16 Correct 53 ms 24184 KB Correct.
17 Correct 58 ms 24416 KB Correct.
18 Correct 52 ms 24440 KB Correct.
19 Correct 54 ms 24056 KB Correct.
20 Correct 48 ms 24400 KB Correct.
21 Correct 57 ms 24280 KB Correct.
22 Correct 53 ms 24184 KB Correct.
23 Correct 73 ms 23928 KB Correct.
24 Correct 46 ms 24432 KB Correct.
25 Correct 67 ms 24300 KB Correct.
26 Correct 49 ms 23800 KB Correct.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12544 KB Correct.
2 Correct 11 ms 12544 KB Correct.
3 Correct 12 ms 12544 KB Correct.
4 Correct 13 ms 12544 KB Correct.
5 Correct 14 ms 12544 KB Correct.
6 Correct 13 ms 12544 KB Correct.
7 Correct 12 ms 12520 KB Correct.
8 Correct 12 ms 12544 KB Correct.
9 Correct 12 ms 12544 KB Correct.
10 Correct 12 ms 12544 KB Correct.
11 Correct 12 ms 12520 KB Correct.
12 Correct 11 ms 12520 KB Correct.
13 Correct 12 ms 12592 KB Correct.
14 Correct 11 ms 12596 KB Correct.
15 Correct 11 ms 12544 KB Correct.
16 Correct 13 ms 12576 KB Correct.
17 Correct 15 ms 12576 KB Correct.
18 Correct 14 ms 12544 KB Correct.
19 Correct 13 ms 12544 KB Correct.
20 Correct 14 ms 12544 KB Correct.
21 Correct 12 ms 12544 KB Correct.
22 Correct 12 ms 12520 KB Correct.
23 Correct 14 ms 12464 KB Correct.
24 Correct 13 ms 15976 KB Correct.
25 Correct 12 ms 14080 KB Correct.
26 Correct 13 ms 15360 KB Correct.
27 Correct 12 ms 13952 KB Correct.
28 Correct 15 ms 13952 KB Correct.
29 Correct 13 ms 13440 KB Correct.
30 Correct 13 ms 13416 KB Correct.
31 Correct 20 ms 15232 KB Correct.
32 Correct 46 ms 24440 KB Correct.
33 Correct 47 ms 23620 KB Correct.
34 Correct 54 ms 23880 KB Correct.
35 Correct 60 ms 24288 KB Correct.
36 Correct 48 ms 23800 KB Correct.
37 Correct 53 ms 24048 KB Correct.
38 Correct 68 ms 24312 KB Correct.
39 Correct 53 ms 24184 KB Correct.
40 Correct 58 ms 24416 KB Correct.
41 Correct 52 ms 24440 KB Correct.
42 Correct 54 ms 24056 KB Correct.
43 Correct 48 ms 24400 KB Correct.
44 Correct 57 ms 24280 KB Correct.
45 Correct 53 ms 24184 KB Correct.
46 Correct 73 ms 23928 KB Correct.
47 Correct 46 ms 24432 KB Correct.
48 Correct 67 ms 24300 KB Correct.
49 Correct 49 ms 23800 KB Correct.
50 Incorrect 2693 ms 262064 KB First line is not correct.
51 Halted 0 ms 0 KB -