Submission #422045

#TimeUsernameProblemLanguageResultExecution timeMemory
422045LptN21Selotejp (COCI20_selotejp)C++14
110 / 110
54 ms40360 KiB
#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 (stderr)

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;
      |         ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...