Submission #1869826

---

Source Code Expand

//while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

const int nax=107;

int n, m;

char wcz[nax];
int twa[nax][nax];

pair <int,int> pin;

int wyn;

int now[nax][nax];
int sum[nax][nax];

void sumsy()
{
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+twa[i][j];
}

inline int daj(int a, int b, int l, int p)
{
	return sum[b][p]-sum[b][l-1]-sum[a-1][p]+sum[a-1][l-1];
}

void obr()
{
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			now[i][j]=twa[i][j];
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			twa[j][n+1-i]=now[i][j];
	swap(pin.first, pin.second);
	pin.second=n+1-pin.second;
}

//~ void symet()
//~ {
	//~ for (int i=1; i<=n; i++)
		//~ for (int j=1; j<=n; j++)
			//~ now[i][j]=twa[i][j];
	//~ for (int i=1; i<=n; i++)
		//~ for (int j=1; j<=n; j++)
			//~ twa[i][n+1-j]=now[i][j];
	//~ pin.second=n+1-pin.second;
//~ }

int dp[nax][nax][nax];

void zwi(int &a, int b)
{
	a=max(a, b);
}

void licz()
{
	//~ wyn=min(wyn, daj(1, pin.first, pin.second, n));
	//~ 
	//~ for (int i=1; i<=pin.first; i++)
	//~ {
		//~ for (int j=pin.second; j<=n; j++)
		//~ {
			//~ int tu=0;
			//~ tu+=daj(i, pin.first, pin.second, j);
			//~ tu+=daj(1, i-1, 1, j);
			//~ tu+=daj(i, n, j+1, n);
			//~ wyn=min(wyn, tu);
		//~ }
	//~ }
	//~ 
	//~ for (int i=1; i<=pin.first; i++)
	//~ {
		//~ for (int ii=i; ii<=pin.first; ii++)
		//~ {
			//~ for (int j=1; j<=pin.second; j++)
			//~ {
				//~ for (int jj=pin.second; jj<=n; jj++)
				//~ {
					//~ int tu=0;
					//~ tu+=daj(i, ii, j, jj);
					//~ tu+=daj(ii+1, pin.first, pin.second, jj);
					//~ tu+=daj(1, i-1, j, n);
					//~ tu+=daj(i, n, 1, j-1);
					//~ tu+=daj(ii+1, n, jj+1, n);
					//~ wyn=min(wyn, tu);
				//~ }
			//~ }
		//~ }
	//~ }
	memset(dp, 0, sizeof(dp));
	
	for (int i=pin.first; i<=n; i++)
	{
		for (int j=1; j<=pin.second; j++)
		{
			for (int l=pin.second; l<=n; l++)
			{
				zwi(dp[i][j][l], daj(1, pin.first-1, j, l)+daj(pin.first, i, pin.second+1, l));
				zwi(dp[i][j][l], daj(1, pin.first-1, j, l)+daj(pin.first, i, j, pin.second-1));
				
				for (int ii=i+1; ii<=n; ii++)
				{
					for (int jj=1; jj<j; jj++)
						zwi(dp[ii][jj][l], dp[i][j][l]+daj(i+1, ii, jj, j-1));
					for (int ll=l+1; ll<=n; ll++)
						zwi(dp[ii][j][ll], dp[i][j][l]+daj(i+1, ii, l+1, ll));
				}
			}
		}
	}
	//debug() << imie(tu);
	wyn=min(wyn, daj(1, n, 1, n)-dp[n][1][n]);
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++)
	{
		scanf("%s", wcz+1);
		for (int j=1; j<=m; j++)
		{
			if (wcz[j]=='P')
				pin={i, j};
			if (wcz[j]=='#')
				twa[i][j]=1;
		}
	}
	n=max(n, m);
	wyn=n*n;
	for (int h=0; h<4; h++)
	{
		//~ for (int p=0; p<2; p++)
		//~ {
			//~ sumsy();
			//~ licz();
			//~ symet();
		//~ }
		sumsy();
		licz();
		obr();
	}
	printf("%d\n", wyn);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:162:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
./Main.cpp:165:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", wcz+1);
                     ^

Judge Result