Submission #219398

#TimeUsernameProblemLanguageResultExecution timeMemory
219398VEGAnnSkandi (COCI20_skandi)C++14
9 / 110
6 ms768 KiB
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() #define sz(x) ((int)x.size()) #define PB push_back #define pii pair<int,int> #define MP make_pair #define ft first #define sd second using namespace std; const int N = 510; const int K = 1520; const int oo = 2e9; const int md = int(1e9) + 7; vector<pii> vc; char c[N][N], cc[N][N]; int n, m, ans = oo, mem; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt","r",stdin); cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> c[i][j]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){ if (c[i][j] == '0') continue; if (i < n - 1 && c[i + 1][j] == '0') vc.PB(MP(i * m + j, 0)); if (j < m - 1 && c[i][j + 1] == '0') vc.PB(MP(i * m + j, 1)); } for (int msk = 0; msk < (1 << sz(vc)); msk++){ int kol = __builtin_popcount(msk); if (kol >= ans) continue; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cc[i][j] = c[i][j]; for (int id = 0; id < sz(vc); id++) if (msk & (1 << id)){ int x = vc[id].ft / m; int y = vc[id].ft % m; if (vc[id].sd){ int yy = y + 1; while (yy < m && c[x][yy] == '0'){ cc[x][yy] = '1'; yy++; } } else { int xx = x + 1; while (xx < n && c[xx][y] == '0'){ cc[xx][y] = '1'; xx++; } } } bool ok = 1; for (int i = 0; i < n && ok; i++) for (int j = 0; j < m && ok; j++) if (cc[i][j] == '0') ok = 0; if (ok && ans > kol){ ans = kol; mem = msk; } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...