oj.uz

Submission #684387

# Submission time Handle Problem Language Result Execution time Memory
684387 2023-01-21T05:42:11 Z vjudge1 Selotejp (COCI20_selotejp) C++17
0 / 110
 12 ms 6076 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int INF = 2e9;
int dp[1001][11][(1<<11)];
char grid[1001][11];
int main()
{
    
    int n, m;
    cin>>n>>m;
    for(int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int mask = 0; mask < (1<<m); mask++) dp[i][j][mask] = INF;
    for(int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
        {
            cin>>grid[i][j];
        }
    }
    for(int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int mask = 0; mask < (1<<m); mask++)
            {
                if(mask & (1<<j)){
                    if(grid[i][j] == '.') dp[i][j][mask] = INF;
                    else dp[i][j][mask] = min(dp[i][j - 1][mask], dp[i][j - 1][(mask ^ (1<<j))] + 1);
                }else{
                    dp[i][j][mask] = min(dp[i][j - 1][mask], dp[i][j - 1][(mask ^ (1<<j))]);
                    if(grid[i][j] == '#' && (j == 0 || grid[i][j - 1] || (mask & (1<<(j - 1))))) dp[i][mask][j]++;
                }
            }
        }
        for (int mask = 0; mask < (1<<n); mask++) dp[i + 1][0][mask] = dp[i][m - 1][mask];
    }
    cout<<*min_element(dp[n - 1][m - 1], dp[n - 1][m - 1] + (1<<m));
}

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6076 KB Output isn't correct
2 Halted 0 ms 0 KB -