oj.uz

Submission #212316

# Submission time Handle Problem Language Result Execution time Memory
212316 2020-03-22T17:06:36 Z model_code Skandi (COCI20_skandi) C++17
25 / 110
 2330 ms 261316 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";
        }

        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:101:9: warning: variable 'last_mask_sol' set but not used [-Wunused-but-set-variable]
     int last_mask_sol = mask_sol;
         ^~~~~~~~~~~~~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
2 Correct 11 ms 12544 KB Correct.
3 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
4 Correct 11 ms 12544 KB Correct.
5 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
7 Correct 12 ms 12544 KB Correct.
8 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
10 Correct 11 ms 12544 KB Correct.
11 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
12 Correct 11 ms 12544 KB Correct.
13 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
18 Correct 11 ms 12544 KB Correct.
19 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 16000 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 14 ms 14080 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 15 ms 15488 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 16 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 15 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 14 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 25 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 41 ms 24576 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 53 ms 23544 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 50 ms 23928 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 54 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 48 ms 23852 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 49 ms 23996 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 58 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 50 ms 24184 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 48 ms 24344 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 61 ms 24544 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 54 ms 24160 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 48 ms 24440 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 50 ms 24200 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 60 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 55 ms 24032 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 48 ms 24444 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 53 ms 24276 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 48 ms 23800 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
2 Correct 11 ms 12544 KB Correct.
3 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
4 Correct 11 ms 12544 KB Correct.
5 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
7 Correct 12 ms 12544 KB Correct.
8 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
10 Correct 11 ms 12544 KB Correct.
11 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
12 Correct 11 ms 12544 KB Correct.
13 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
18 Correct 11 ms 12544 KB Correct.
19 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 11 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 13 ms 16000 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 14 ms 14080 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 15 ms 15488 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 12 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 16 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 15 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 14 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 25 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 41 ms 24576 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 53 ms 23544 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 50 ms 23928 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 54 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 48 ms 23852 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 49 ms 23996 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 58 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 50 ms 24184 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 48 ms 24344 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 61 ms 24544 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 54 ms 24160 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 48 ms 24440 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 50 ms 24200 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 60 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 55 ms 24032 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 48 ms 24444 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 53 ms 24276 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 48 ms 23800 KB First line is correct, but the reconstruction is not properly formatted.
50 Incorrect 2330 ms 261316 KB First line is not correct.
51 Halted 0 ms 0 KB -