| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 854650 | 2023-09-28T10:20:39 Z | efedmrlr | Selotejp (COCI20_selotejp) | C++17 | 1000 ms | 604 KB |
#include <bits/stdc++.h>
using namespace std;
#define n_l '\n'
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)), __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); }
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e3+5;
const int M = 11;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
int n,m,q;
vector<int> dp, dpnew, subsums;
vector<vector<int> > grid;
vector<int> pow3(M);
inline array<int,2> find2(int x) {
array<int,2> res = {0, -1};
int ind = 0;
while(x>0) {
int el = x % 3;
if(el == 2) {
res[1] = ind;
}
else {
res[0] += el * (1<<ind);
}
ind++;
x /= 3;
}
return res;
}
inline void find_subs() { //O(3^m)
for(int i = 0; i<pow3[m]; i++) {
auto popc = find2(i);
if(popc[1] == -1) {
subsums[i] = dp[popc[0]];
}
else {
subsums[i] = min(subsums[i - pow3[ popc[1] ]] , subsums[i - (pow3[ popc[1] ] * 2)] );
}
}
}
inline void solve() {
cin>>n>>m;
dp.assign((1<<m) , INF);
dpnew.assign((1<<m), INF);
grid.resize(n, vector<int> (m));
subsums.resize(pow3[m]);
for(int i = 0; i<n; i++) {
for(int j = 0; j<m; j++) {
char tmp;
cin>>tmp;
grid[i][j] = (tmp == '#') ? 0 : 1;
}
}
dp[0] = 0;
find_subs();
for(int i = 0; i<n; i++) {
for(int mask = 0; mask < (1<<m); mask++) {
bool flag = 0;
for(int j = 0; j<m; j++) {
if(grid[i][j] && (mask & (1<<j)) ) {
dpnew[mask] = INF;
flag = 1;
break;
}
}
if(flag) continue;
for(int lm = mask; ; lm = (lm - 1) & mask) {
if(dp[lm] == INF) continue;
int cnt = 0;
vector<int> walls = grid[i];
for(int j = 0; j<m; j++){
if((mask & (1<<j)) && !(lm & (1<<j)) ) {
cnt++;
walls[j] = 1;
}
else if( (mask & (1<<j)) && (lm & (1<<j)) ) {
walls[j] = 1;
}
}
int last = -1;
for(int j = 0; j<m; j++) {
if(walls[j]) {
if(j > last + 1) {
cnt++;
}
last = j;
}
}
if(last != m-1) {
cnt++;
}
int num = 0;
for(int j = 0; j<m; j++) {
if((1<<j) & mask) {
bool tmp = (1<<j) & lm;
num += tmp * pow3[j];
}
else {
num += 2 * pow3[j];
}
}
dpnew[mask] = min(dpnew[mask] , cnt + subsums[num]);
if(lm == 0) break;
}
}
dp = dpnew;
find_subs();
dpnew.assign((1<<m), INF);
}
int ans = INF;
for(int i = 0; i<(1<<m); i++) ans = min(ans, dp[i]);
cout<<ans<<"\n";
}
signed main() {
pow3[0] = 1;
for(int i = 1; i<M; i++) {
pow3[i] = pow3[i-1] * 3;
}
fastio();
int test = 1;
//cin>>test;
while(test--) {
solve();
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 348 KB | Output is correct |
| 2 | Execution timed out | 1034 ms | 604 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 600 KB | Output is correct |
| 2 | Correct | 15 ms | 604 KB | Output is correct |
| 3 | Correct | 13 ms | 604 KB | Output is correct |
| 4 | Correct | 18 ms | 604 KB | Output is correct |
| 5 | Correct | 14 ms | 604 KB | Output is correct |
| 6 | Correct | 12 ms | 600 KB | Output is correct |
| 7 | Correct | 4 ms | 348 KB | Output is correct |
| 8 | Correct | 15 ms | 604 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 348 KB | Output is correct |
| 2 | Execution timed out | 1034 ms | 604 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |