oj.uz

Submission #866378

# Submission time Handle Problem Language Result Execution time Memory
866378 2023-10-26T03:23:49 Z vjudge1 Selotejp (COCI20_selotejp) C++17
110 / 110
 31 ms 88520 KB 
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define endl "\n"

const int N = 10;
const int p = 1e9 + 7;

ll dp[1001][11][1<<10];
vector<string> vec(1001);




void solve(){
    int n, m;
    cin >> n >> m;
    int mask = 1 << m;
    for(int i = 0; i < m; i++){
        vec[0] += '.';
    }
    for(int i = 1; i <= n; i++){
        cin >> vec[i];
    }
    for(int i = 0; i < mask; i++){
        dp[0][m][i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k < mask; k++){
                int nm = k ^ (1 << (j - 1));
                if(vec[i][j - 1] == '#'){
                    if(k & (1 << (j - 1))){
                        if(j == 1){
                            dp[i][j][k] = min(dp[i - 1][m][k], dp[i - 1][m][nm]) + 1;
                            if(vec[i - 1][j - 1] == '#'){
                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][m][k]);
                            }
                        }else{
                            dp[i][j][k] = min(dp[i][j - 1][k], dp[i][j - 1][nm]) + 1;
                            if(vec[i - 1][j - 1] == '#'){
                                dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k]);
                            }
                        }
                    }else{
                        if(j == 1){
                            dp[i][j][k] =  min(dp[i - 1][m][k], dp[i - 1][m][nm]) + 1;
                        }else{
                            dp[i][j][k] = min(dp[i][j - 1][k], dp[i][j - 1][nm]) + 1;
                            if(vec[i][j - 2] == '#' && (k & (1 << (j - 2))) == 0){
                                dp[i][j][k] -= 1;
                            }
                        }
                    }
                }else{
                    if(j == 1){
                        dp[i][j][k] = min(dp[i - 1][m][k], dp[i - 1][m][nm]);
                    }else{
                        dp[i][j][k] = min(dp[i][j - 1][k], dp[i][j - 1][nm]);
                    }
                }
            }
        }
    }
    ll res = n*m;
    for(int i = 0; i < mask; i++){
        res = min(res, dp[n][m][i]);
    }
    cout << res << endl;
    
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 26 ms 82632 KB Output is correct
3 Correct 11 ms 82520 KB Output is correct
4 Correct 16 ms 86620 KB Output is correct
5 Correct 25 ms 87128 KB Output is correct
6 Correct 25 ms 87380 KB Output is correct
7 Correct 25 ms 86620 KB Output is correct
8 Correct 21 ms 82604 KB Output is correct
9 Correct 23 ms 82592 KB Output is correct
10 Correct 26 ms 88520 KB Output is correct

Subtask #2
35.0 / 35.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 26 ms 82632 KB Output is correct
3 Correct 11 ms 82520 KB Output is correct
4 Correct 16 ms 86620 KB Output is correct
5 Correct 25 ms 87128 KB Output is correct
6 Correct 25 ms 87380 KB Output is correct
7 Correct 25 ms 86620 KB Output is correct
8 Correct 21 ms 82604 KB Output is correct
9 Correct 23 ms 82592 KB Output is correct
10 Correct 26 ms 88520 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2544 KB Output is correct
19 Correct 9 ms 86616 KB Output is correct
20 Correct 12 ms 86876 KB Output is correct
21 Correct 17 ms 88156 KB Output is correct
22 Correct 22 ms 86732 KB Output is correct
23 Correct 23 ms 86616 KB Output is correct
24 Correct 23 ms 86608 KB Output is correct
25 Correct 30 ms 86864 KB Output is correct
26 Correct 28 ms 84572 KB Output is correct
27 Correct 30 ms 84564 KB Output is correct
28 Correct 31 ms 86620 KB Output is correct