Submission #1105034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105034		InvMOD	Selotejp (COCI20_selotejp)	C++14	110 / 110	20 ms	524 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3+5, M = 11;

int n, m, a[N][M];

namespace Sub1{
    bool check(){
        return m * n * (1<<m) <= 1e5;
    }

    const int inf = 1e9;

    void solve()
    {
        vector<vector<int>> dp(n+1, vector<int>((1<<m), inf));

        dp[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int curmask = 0; curmask < (1<<m); curmask++){
                // Check can create curmask
                bool skip = false;
                for(int j = 0; j < m; j++){
                    if(a[i][j] && (curmask>>j&1)){
                        skip = true;
                        break;
                    }
                }

                if(skip) continue;

                for(int premask = 0; premask < (1<<m); premask++){
                    skip = false;
                    for(int j = 0; j < m; j++){
                        if(a[i-1][j] && (premask>>j&1)){
                            skip = true;
                            break;
                        }
                    }

                    if(skip) continue;

                    int cost = 0;
                    vector<bool> die(m, false);
                    for(int j = 0; j < m; j++){
                        if(curmask>>j&1){
                            if(!(premask>>j&1)){
                                cost++;
                            }
                            die[j] = true;
                        }
                        if(a[i][j]) die[j] = true;
                    }

                    for(int j = 0; j < m; j++){
                        if(!die[j]){
                            if(j){
                                cost += (die[j-1]);
                            }
                            else cost++;
                        }
                    }

                    dp[i][curmask] = min(dp[i][curmask], dp[i-1][premask] + cost);
                    //cout << bitset<3>(curmask) <<" " << dp[i][curmask] <<" " << bitset<3>(premask) <<" " << dp[i-1][premask] <<" " << cost <<"\n";
                }
            }
        }

        int answer = inf;
        for(int i = 0; i < (1<<m); i++) answer = min(answer, dp[n][i]);

        cout << answer <<"\n";
    }
}

namespace Sub2{

    const int inf = 1e9;

    void solve()
    {
        vector<int> dp((1<<m), inf), f((1<<m), inf);

        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < m; j++){
                for(int mask = 0; mask < (1<<m); mask++){
                    if(!(mask>>j&1)){
                        // a[i][j] use horizontal line => a[i-1][j] can use horizontal or vertical line
                        f[mask] = min(dp[mask], dp[mask^(1<<j)]);

                        // We have to add 1 to cost
                        if(!a[i][j] && (!j || ((mask>>(j-1))&1) || a[i][j-1])) f[mask]++;
                    }
                    else{
                        // if we cant add vertical here because of some shit >:(
                        // a[i][j] use horizontal line => a[i-1][j] use vertical or a[i-1][j] use horizontal and plus one vertical
                        if(a[i][j]){
                            f[mask] = inf;
                        }
                        else f[mask] = min(dp[mask], dp[mask^(1<<j)] + 1);
                    }
                }

                swap(dp, f);
            }
        }

        int answer = inf;
        for(int mask = 0; mask < (1<<m); mask++){
            answer = min(answer, dp[mask]);
        }

        cout << answer <<"\n";
        return;
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < m; j++){
            char c; cin >> c;
            a[i][j] = (c == '.');
        }
    }
    Sub2::solve(); return;

    if(Sub1::check()){
        Sub1::solve();
    }
    else{
        Sub2::solve();
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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