Submission #706885

#	Time	Username	Problem	Language	Result	Execution time	Memory
706885		YugiHacker	Selotejp (COCI20_selotejp)	C++14	110 / 110	21 ms	352 KiB

Main

/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn
#define bit(n,i) ((n>>i)&1)
using namespace std;
int n, m;
char a[1003][11];
vector <int> f, pre;
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    f0 (i, n) f0 (j, m) cin >> a[i][j];
    f.resize(1 << m), pre.resize(1 << m, 1e5);
    pre[0] = 0;
    f0 (i, n) f0 (j, m)
    {
        f0 (mask, 1 << m)
        {
            if (bit(mask, j))
            {
                if (a[i][j] == '.') f[mask] = 1e5; // ?
                else f[mask] = min(pre[mask], pre[mask ^ (1 << j)] + 1);
                // #
                // v
                // #
            }
            else
            {
                if (a[i][j] == '.')
                    f[mask] = min(pre[mask], pre[mask ^ (1 << j)]);
                else if (j && a[i][j] == '#' && a[i][j-1] == '#' && bit(mask, j-1) == 0)
                    f[mask] = min(pre[mask], pre[mask ^ (1 << j)]); // # -> #
                else
                    f[mask] = min(pre[mask], pre[mask ^ (1 << j)]) + 1;
            }
        }
        pre = f;
    }
    cout << *min_element(pre.begin(), pre.end());
}
/*
5 8
#.##..#.
....###.
#.#.##..
#.#..#.#
##..####
*/

Compilation message (stderr)

Main.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:40:80: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   40 |                 else if (j && a[i][j] == '#' && a[i][j-1] == '#' && bit(mask, j-1) == 0)
      |                                                                               ~^~
Main.cpp:10:23: note: in definition of macro 'bit'
   10 | #define bit(n,i) ((n>>i)&1)
      |                       ^

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