oj.uz

Submission #956196

# Submission time Handle Problem Language Result Execution time Memory
956196 2024-04-01T09:47:44 Z kigash Selotejp (COCI20_selotejp) C++17
110 / 110
 28 ms 33372 KB 
#include "bits/stdc++.h"
using namespace std;       

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN;
const ll mod = 1e9+7, N = 2e3+5;
ll dp[N][2][N];
string s[N];

void yesyesyes() {
    ll n, m;
    cin>>n>>m;
    for(ll i=0; i<n; i++) cin>>s[i];
    for(ll mask=0; mask<(1<<m); mask++) dp[0][0][mask] = (s[0][0]=='#');
    for(ll i=0; i<n; i++) {
        for(ll j=0; j<m; j++) {
            if(!i && !j) continue;
            for(ll mask=0; mask<(1<<m); mask++) {
                ll mn = inf;
                if(s[i][j]=='.') {
                    if(j) mn = min({mn, dp[i][(j-1)%2][mask], dp[i][(j-1)%2][mask^(1<<j)]});
                    else mn = min({mn, dp[i-1][(m-1)%2][mask], dp[i-1][(m-1)%2][mask^(1<<j)]});
                    dp[i][j%2][mask] = mn;
                    continue;
                }
                if(mask&(1<<j)) {
                    ll add = 1;
                    if(j && s[i][j-1]=='#' && (mask&(1<<(j-1)))>0) add = 0;
                    if(j) mn = min({mn, dp[i][(j-1)%2][mask]+add, dp[i][(j-1)%2][mask^(1<<j)]+add});
                    else mn = min({mn, dp[i-1][(m-1)%2][mask]+1, dp[i-1][(m-1)%2][mask^(1<<j)]+1});
                    dp[i][j%2][mask] = mn;
                }
                else {
                    if(i && s[i-1][j]=='#') {
                        if(j) mn = min(mn, dp[i][(j-1)%2][mask]);
                        else mn = min(mn, dp[i-1][(m-1)%2][mask]);
                    }
                    if(j) mn = min({mn, dp[i][(j-1)%2][mask]+1, dp[i][(j-1)%2][mask^(1<<j)]+1});
                    else mn = min({mn, dp[i-1][(m-1)%2][mask]+1, dp[i-1][(m-1)%2][mask^(1<<j)]+1});
                    dp[i][j%2][mask] = mn;
                }
            }
        }
    }
    ll ans = MX;
    for(ll mask=0; mask<(1<<m); mask++) ans = min(ans, dp[n-1][(m-1)%2][mask]);
    cout<<ans<<"\n";
    return;
}

signed main(/*Kigash Amir*/) {
    // freopen("");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) {
        yesyesyes();
    }
}

Compilation message

Main.cpp: In function 'void freopen(std::string)':
Main.cpp:17:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:73: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2552 KB Output is correct
2 Correct 25 ms 31368 KB Output is correct
3 Correct 9 ms 31320 KB Output is correct
4 Correct 12 ms 31324 KB Output is correct
5 Correct 23 ms 31380 KB Output is correct
6 Correct 24 ms 33364 KB Output is correct
7 Correct 23 ms 31324 KB Output is correct
8 Correct 21 ms 31324 KB Output is correct
9 Correct 22 ms 31400 KB Output is correct
10 Correct 25 ms 33360 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2584 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2576 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2552 KB Output is correct
2 Correct 25 ms 31368 KB Output is correct
3 Correct 9 ms 31320 KB Output is correct
4 Correct 12 ms 31324 KB Output is correct
5 Correct 23 ms 31380 KB Output is correct
6 Correct 24 ms 33364 KB Output is correct
7 Correct 23 ms 31324 KB Output is correct
8 Correct 21 ms 31324 KB Output is correct
9 Correct 22 ms 31400 KB Output is correct
10 Correct 25 ms 33360 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2584 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2576 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 5 ms 31324 KB Output is correct
20 Correct 10 ms 33368 KB Output is correct
21 Correct 15 ms 33372 KB Output is correct
22 Correct 24 ms 31316 KB Output is correct
23 Correct 23 ms 31312 KB Output is correct
24 Correct 26 ms 31448 KB Output is correct
25 Correct 24 ms 31336 KB Output is correct
26 Correct 26 ms 31324 KB Output is correct
27 Correct 27 ms 31320 KB Output is correct
28 Correct 28 ms 31364 KB Output is correct