oj.uz

Submission #422045

# Submission time Handle Problem Language Result Execution time Memory
422045 2021-06-09T16:01:01 Z LptN21 Selotejp (COCI20_selotejp) C++14
110 / 110
 54 ms 40360 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
#define all(a) (a).begin(), (a).end()
#define odd(x) __builtin_parity((int)x)
#define cntbit(x) __builtin_popcount(x)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ll, ii> i3;
const int N = 1000+7, M=10;
const ll MOD = 1e9+7;
const int oo = 1e9;

int MASK;

int n, m, k, t, d;

int a[N], _dp[N][M][1024];

bool check(int i, int j) {return i&(1<<j);}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    scanf("%d%d", &n, &m); t=oo;
    char ch[m]; MASK=(1<<m);
    for(int i=1;i<=n;i++) {
        scanf("%s", &ch); a[i] = 0;
        for(int j=0;j<m;j++) a[i]=2*a[i]+(ch[j]=='#');
    }
    for(int k=1;k<=n;k++) for(int j=0;j<m;j++) for(int i=0;i<MASK;i++) {
        if(i&(1<<j)) {
            if(!check(a[k], j)) _dp[k][j][i]=oo;
            else if(!j) _dp[k][j][i]=min((k==1?oo:_dp[k-1][m-1][i]), _dp[k-1][m-1][i^(1<<j)]+1);
            else _dp[k][j][i]=min(_dp[k][j-1][i]+(k==1), _dp[k][j-1][i^(1<<j)]+1);
        } else {
            if(!j) _dp[k][j][i]=min(_dp[k-1][m-1][i], _dp[k-1][m-1][i^(1<<j)])+check(a[k], j);
            else {
                if(!check(a[k], j)||(check(a[k], j-1)&&!check(i, j-1)))
                    _dp[k][j][i]=min(_dp[k][j-1][i], _dp[k][j-1][i^(1<<j)]);
                else _dp[k][j][i]=min(_dp[k][j-1][i], _dp[k][j-1][i^(1<<j)])+1;
            }
        }
    }
    for(int i=0;i<MASK;i++) t=min(t, _dp[n][m-1][i]);
    printf("%d", t);
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[m]' [-Wformat=]
   36 |         scanf("%s", &ch); a[i] = 0;
      |                ~^   ~~~
      |                 |   |
      |                 |   char (*)[m]
      |                 char*
Main.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d", &n, &m); t=oo;
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%s", &ch); a[i] = 0;
      |         ~~~~~^~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 46 ms 37156 KB Output is correct
3 Correct 19 ms 29796 KB Output is correct
4 Correct 25 ms 35248 KB Output is correct
5 Correct 40 ms 39620 KB Output is correct
6 Correct 41 ms 39748 KB Output is correct
7 Correct 40 ms 38784 KB Output is correct
8 Correct 36 ms 37148 KB Output is correct
9 Correct 39 ms 37324 KB Output is correct
10 Correct 42 ms 40360 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 552 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 46 ms 37156 KB Output is correct
3 Correct 19 ms 29796 KB Output is correct
4 Correct 25 ms 35248 KB Output is correct
5 Correct 40 ms 39620 KB Output is correct
6 Correct 41 ms 39748 KB Output is correct
7 Correct 40 ms 38784 KB Output is correct
8 Correct 36 ms 37148 KB Output is correct
9 Correct 39 ms 37324 KB Output is correct
10 Correct 42 ms 40360 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 584 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 552 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 9 ms 19660 KB Output is correct
20 Correct 21 ms 31968 KB Output is correct
21 Correct 28 ms 36268 KB Output is correct
22 Correct 36 ms 39044 KB Output is correct
23 Correct 36 ms 38852 KB Output is correct
24 Correct 38 ms 38592 KB Output is correct
25 Correct 42 ms 39524 KB Output is correct
26 Correct 44 ms 37836 KB Output is correct
27 Correct 46 ms 37928 KB Output is correct
28 Correct 54 ms 39232 KB Output is correct