Submission #379199

#	Time	Username	Problem	Language	Result	Execution time	Memory
379199		maomao90	Selotejp (COCI20_selotejp)	C++14	110 / 110	47 ms	41416 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define mnto(x, y) x = min(x, (__typeof__(x)) y)
#define mxto(x, y) x = max(x, (__typeof__(x)) y)
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;

#define MAXN 1005
#define MAXM 10
#define MAXPOW 1050
#define INF 1000000005

int n, m;
char grid[MAXN][MAXM];
int dp[MAXN][MAXM][MAXPOW];
int ansi = -1, ansj;

int main() {
	scanf("%d%d", &n, &m);
	REP (i, 1, n + 1) {
		scanf(" %s", &grid[i]);
	}
	REP (j, 0, m) {
		REP (msk, 0, 1 << m) {
			dp[0][j][msk] = msk == 0 ? 0 : INF;
		}
	}
	REP (i, 1, n + 1) {
		REP (j, 0, m) {
			if (grid[i][j] == '#') {
				ansi = i;
				ansj = j;
			}
			int prvj = j - 1, prvi = i;
			if (prvj < 0) {
				prvj = m - 1;
				prvi--;
			}
			REP (msk, 0, 1 << m) {
				if (msk & (1 << j)) {
					if (grid[i][j] == '.') {
						dp[i][j][msk] = INF;
					} else {
						dp[i][j][msk] = min(dp[prvi][prvj][msk], dp[prvi][prvj][msk ^ (1 << j)] + 1);
					}
				} else {
					dp[i][j][msk] = min(dp[prvi][prvj][msk], dp[prvi][prvj][msk ^ (1 << j)]);
					if (grid[i][j] == '.') continue;
					if (j == 0 || grid[i][j - 1] == '.' || msk & (1 << j - 1)) dp[i][j][msk]++;
				}
			}
		}
	}
	int ans = INF;
	if (ansi == -1) ans = 0;
	else {
		REP (msk, 0, 1 << m) {
			ans = min(dp[ansi][ansj][msk], ans);
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*
2 3
#.#
###

4 3
.#.
###
.##
.#.

4 4
####
#.#.
#.##
####
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:12: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
   35 |   scanf(" %s", &grid[i]);
      |           ~^   ~~~~~~~~
      |            |   |
      |            |   char (*)[10]
      |            char*
Main.cpp:63:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |      if (j == 0 || grid[i][j - 1] == '.' || msk & (1 << j - 1)) dp[i][j][msk]++;
      |                                                         ~~^~~
Main.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf(" %s", &grid[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40