Submission #377577

#	Time	Username	Problem	Language	Result	Execution time	Memory
377577		ne4eHbKa	Selotejp (COCI20_selotejp)	C++17	110 / 110	76 ms	40428 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

void solve() {
    int n, m;
    cin >> n >> m;
    bool mp[n][m];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            char c; cin >> c;
            mp[i][j] = c == '#';
        }
    }
    int k = 1 << m;
    int dp[n + 1][m][k];
    memset(dp, 127, sizeof dp);
    dp[0][0][0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            for(int ms = 0; ms < k; ++ms) {
                int c = dp[i][j][ms];
                if(c > +inf) continue;
                int nxj = j + 1, nxi = i;
                if(nxj == m) nxj = 0, ++nxi;
                if(mp[i][j]) {
                    umin(dp[nxi][nxj][ms | 1 << j], c + !(1 << j & ms));
                    umin(dp[nxi][nxj][ms & ~(1 << j)], c + (!j || !mp[i][j - 1] || (ms & 1 << j - 1)));
                } else {
                    umin(dp[nxi][nxj][ms & ~(1 << j)], c);
                }
            }
        }
    }
    int ans = +inf;
    for(int i = 0; i < k; ++i)
        umin(ans, dp[n][0][i]);
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:53:97: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |                     umin(dp[nxi][nxj][ms & ~(1 << j)], c + (!j || !mp[i][j - 1] || (ms & 1 << j - 1)));
      |                                                                                               ~~^~~

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