Submission #498984

#TimeUsernameProblemLanguageResultExecution timeMemory
498984VictorSelotejp (COCI20_selotejp)C++17
110 / 110
186 ms81728 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; int rows, cols, memo[1001][1 << 10][10][2]; string grid[1001]; int turn_off(int mask, int col) { return mask & ((1 << cols) - 1 - (1 << col)); } int dp(int row, int mask, int col, int prev) { if (row == rows) return 0; int &ans = memo[row][mask][col][prev]; if (ans != -1) return ans; int ncol = col + 1, nrow = row; if (ncol == cols) { ncol = 0; ++nrow; } if (grid[row][col] == '.') { ans = dp(nrow, turn_off(mask, col), ncol, 0); } else { int add = !prev; ans = dp(nrow, turn_off(mask, col), ncol, 1 && ncol) + add; add = (mask & (1 << col)) == 0; ans = min(ans, dp(nrow, mask | (1 << col), ncol, 0) + add); //cout << "row = " << row << " mask = " << mask << " col = " << col << " prev = " << prev<<" ans = "<<ans << endl; } return ans; } void print_dp(int row, int mask,int col,int prev) { if(row==rows)return; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); memset(memo, -1, sizeof(memo)); cin >> rows >> cols; rep(i, 0, rows) cin >> grid[i]; cout << dp(0, 0, 0, 0) << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...