Submission #1180228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180228		miniob	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	1734 ms	258664 KiB

Main

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

int cura[5][5];
int n, m;

int main() 
{
	cin >> n >> m;
    bool czy_obr = false;
    if(n > m)
    {
        czy_obr = true;
        swap(n, m);
    }
	int a[n + 7][m + 7];
	int ile_wchodzi[n + 7][m + 7][3][3][3][3];//gora dol lewo prawo
	int ile_wchodzi_pref[n + 7][m + 7][3][3][3][3];//gora dol lewo prawo
	int pref[m + 7][9];//gora dol lewo prawo
    if(!czy_obr)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
            }
        }
    }
    else
    {
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                cin >> a[n - j + 1][i];
            }
        }
    }
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int gora = 0; gora < 3; gora++)
			{
				for(int dol = 0; dol < 3; dol++)
				{
					for(int lewo = 0; lewo < 3; lewo++)
					{
						for(int prawo = 0; prawo < 3; prawo++)
						{
							for(int i2 = 0; i2 < 5; i2++)
							{
								for(int j2 = 0; j2 < 5; j2++)
								{
									cura[i2][j2] = -1;
								}
							}
							cura[2][2] = a[i][j];
							if(gora >= 1 && i + 1 <= n)
							{
								cura[3][2] = a[i + 1][j];
							}
							if(gora == 2 && i + 2 <= n)
							{
								cura[4][2] = a[i + 2][j];
							}
							if(dol >= 1 && i - 1 >= 1)
							{
								cura[1][2] = a[i - 1][j];
							}
							if(dol == 2 && i - 2 >= 1)
							{
								cura[0][2] = a[i - 2][j];
							}
							if(prawo >= 1 && j + 1 <= m)
							{
								cura[2][3] = a[i][j + 1];
							}
							if(prawo == 2 && j + 2 <= m)
							{
								cura[2][4] = a[i][j + 2];
							}
							if(lewo >= 1 && j - 1 >= 1)
							{
								cura[2][1] = a[i][j - 1];
							}
							if(lewo == 2 && j - 2 >= 1)
							{
								cura[2][0] = a[i][j - 2];
							}
							if(lewo >= 1 && j - 1 >= 1 && gora >= 1 && i + 1 <= n)
							{
								cura[3][1] = a[i + 1][j - 1];
							}
							if(lewo >= 1 && j - 1 >= 1 && dol >= 1 && i - 1 >= 1)
							{
								cura[1][1] = a[i - 1][j - 1];
							}
							if(prawo >= 1 && j + 1 <= m && gora >= 1 && i + 1 <= n)
							{
								cura[3][3] = a[i + 1][j + 1];
							}
							if(prawo >= 1 && j + 1 <= m && dol >= 1 && i - 1 >= 1)
							{
								cura[1][3] = a[i - 1][j + 1];
							}
							/*if(i == 3 && j == 1 && gora == 0 && dol == 1 && lewo == 0 && prawo == 1)
							{
								for(int i2 = 0; i2 < 5; i2++)
								{
									for(int j2 = 0; j2 < 5; j2++)
									{
										cout << cura[i2][j2] << " ";
									}
									cout << endl;
								}			
							}*/
							vector<pair<int,int>> sas;
							sas.push_back({1, 0});
							sas.push_back({-1, 0});
							sas.push_back({0, 1});
							sas.push_back({0, -1});
							int curi, curj;
							curi = curj = 2;
							for(auto x : sas)
							{
								curi += x.first;
								curj += x.second;
								int maxm = 0;
								int curwys = cura[curi][curj];
								for(auto y : sas)
								{
									curi += y.first;
									curj += y.second;
									if(cura[curi][curj] != -1 && cura[curi][curj] < curwys)
									{
										maxm = max(maxm, cura[curi][curj]);
									}
									curi -= y.first;
									curj -= y.second;
								}
								if(cura[curi][curj] == -1)
								{
									maxm = -2137;
								}
								/*if(i == 3 && j == 1 && gora == 0 && dol == 1 && lewo == 0 && prawo == 1)
								{
									cout << cura[curi][curj] << " " << minw << endl;
								}*/
								curi -= x.first;
								curj -= x.second;
								if(cura[2][2] == maxm)
								{
									ile_wchodzi[i][j][gora][dol][lewo][prawo]++;
								}
							}
							/*if(i == 2 && j == 1 && gora == 1 && dol == 0 && lewo == 0 && prawo == 0)
							{
								cout << ile_wchodzi[i][j][gora][dol][lewo][prawo] << endl;
							}*/
							if(ile_wchodzi[i][j][gora][dol][lewo][prawo] != 1)
							{
								ile_wchodzi[i][j][gora][dol][lewo][prawo] = 1;
							}
							else
							{
								ile_wchodzi[i][j][gora][dol][lewo][prawo] = 0;
							}
						}
					}
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int gora = 0; gora < 3; gora++)
			{
				for(int dol = 0; dol < 3; dol++)
				{
					for(int lewo = 0; lewo < 3; lewo++)
					{
						for(int prawo = 0; prawo < 3; prawo++)
						{
							ile_wchodzi_pref[i][j][gora][dol][lewo][prawo] = ile_wchodzi_pref[i - 1][j][gora][dol][lewo][prawo] + ile_wchodzi[i][j][gora][dol][lewo][prawo];
						}
					}
				}
			}
		}
	}
	int odp = 0;
	//cout << czymoze(ile_wchodzi, 2, 1, 3, 2) << endl;
	for(int i = 1; i <= n; i++)
	{
		for(int i2 = i; i2 <= n; i2++)
		{
			int lewlew[m + 7];
			int lewpraw[m + 7];
			int prawlew[m + 7];
			int prawpraw[m + 7];
            int lewm[m + 7];
			int prawm[m + 7];
			int sr[m + 7];
            int srm[m + 7];
            int sama_kol[m + 7];
			int srpref[m + 7];
			srpref[0] = 0;
			map<int, int> f;
			queue<int> q;
			for(int j = 1; j <= m; j++)
			{
				if(i2 - i == 0)
				{
					lewlew[j] = ile_wchodzi[i][j][0][0][0][2];
					lewpraw[j] = ile_wchodzi[i][j][0][0][1][2];
					prawlew[j] = ile_wchodzi[i][j][0][0][2][1];
					prawpraw[j] = ile_wchodzi[i][j][0][0][2][0];
                    lewm[j] = ile_wchodzi[i][j][0][0][0][1];
                    prawm[j] = ile_wchodzi[i][j][0][0][1][0];
					sr[j] = ile_wchodzi[i][j][0][0][2][2];
                    srm[j] = ile_wchodzi[i][j][0][0][1][1];
                    sama_kol[j] = 1;
					srpref[j] = srpref[j - 1] + sr[j];
				}
				if(i2 - i == 1)
				{
					lewlew[j] = ile_wchodzi[i + 1][j][0][1][0][2] + ile_wchodzi[i][j][1][0][0][2];
					lewpraw[j] = ile_wchodzi[i + 1][j][0][1][1][2] + ile_wchodzi[i][j][1][0][1][2];
					prawlew[j] = ile_wchodzi[i + 1][j][0][1][2][1] + ile_wchodzi[i][j][1][0][2][1];
					prawpraw[j] = ile_wchodzi[i + 1][j][0][1][2][0] + ile_wchodzi[i][j][1][0][2][0];
                    lewm[j] = ile_wchodzi[i + 1][j][0][1][0][1] + ile_wchodzi[i][j][1][0][0][1];
                    prawm[j] = ile_wchodzi[i + 1][j][0][1][1][0] + ile_wchodzi[i][j][1][0][1][0];
					sr[j] = ile_wchodzi[i + 1][j][0][1][2][2] + ile_wchodzi[i][j][1][0][2][2];
                    srm[j] =  ile_wchodzi[i + 1][j][0][1][1][1] + ile_wchodzi[i][j][1][0][1][1];
                    sama_kol[j] = 1;
					srpref[j] = srpref[j - 1] + sr[j];
				}
				if(i2 - i == 2)
				{
					lewlew[j] = ile_wchodzi[i + 2][j][0][2][0][2] + ile_wchodzi[i + 1][j][1][1][0][2] + ile_wchodzi[i][j][2][0][0][2];
					lewpraw[j] = ile_wchodzi[i + 2][j][0][2][1][2] + ile_wchodzi[i + 1][j][1][1][1][2] + ile_wchodzi[i][j][2][0][1][2];
					prawlew[j] = ile_wchodzi[i + 2][j][0][2][2][1] + ile_wchodzi[i + 1][j][1][1][2][1] + ile_wchodzi[i][j][2][0][2][1];
					prawpraw[j] = ile_wchodzi[i + 2][j][0][2][2][0] + ile_wchodzi[i + 1][j][1][1][2][0] + ile_wchodzi[i][j][2][0][2][0];
                    lewm[j] = ile_wchodzi[i + 2][j][0][2][0][1] + ile_wchodzi[i + 1][j][1][1][0][1] + ile_wchodzi[i][j][2][0][0][1];
                    prawm[j] = ile_wchodzi[i + 2][j][0][2][1][0] + ile_wchodzi[i + 1][j][1][1][1][0] + ile_wchodzi[i][j][2][0][1][0];
					sr[j] = ile_wchodzi[i + 2][j][0][2][2][2] + ile_wchodzi[i + 1][j][1][1][2][2] + ile_wchodzi[i][j][2][0][2][2];
                    srm[j] =  ile_wchodzi[i + 2][j][0][2][1][1] + ile_wchodzi[i + 1][j][1][1][1][1] + ile_wchodzi[i][j][2][0][1][1];
                    sama_kol[j] = ile_wchodzi[i + 2][j][0][2][0][0] + ile_wchodzi[i + 1][j][1][1][0][0] + ile_wchodzi[i][j][2][0][0][0];
					srpref[j] = srpref[j - 1] + sr[j];
				}
				if(i2 - i == 3)
				{
					lewlew[j] = ile_wchodzi[i + 3][j][0][2][0][2] + ile_wchodzi[i + 2][j][1][2][0][2] + ile_wchodzi[i + 1][j][2][1][0][2] + ile_wchodzi[i][j][2][0][0][2];
					lewpraw[j] = ile_wchodzi[i + 3][j][0][2][1][2] + ile_wchodzi[i + 2][j][1][2][1][2] + ile_wchodzi[i + 1][j][2][1][1][2] + ile_wchodzi[i][j][2][0][1][2];
					prawlew[j] = ile_wchodzi[i + 3][j][0][2][2][1] + ile_wchodzi[i + 2][j][1][2][2][1] + ile_wchodzi[i + 1][j][2][1][2][1] + ile_wchodzi[i][j][2][0][2][1];
					prawpraw[j] = ile_wchodzi[i + 3][j][0][2][2][0] + ile_wchodzi[i + 2][j][1][2][2][0] + ile_wchodzi[i + 1][j][2][1][2][0] + ile_wchodzi[i][j][2][0][2][0];
                    lewm[j] = ile_wchodzi[i + 3][j][0][2][0][1] + ile_wchodzi[i + 2][j][1][2][0][1] + ile_wchodzi[i + 1][j][2][1][0][1] + ile_wchodzi[i][j][2][0][0][1];
                    prawm[j] = ile_wchodzi[i + 3][j][0][2][1][0] + ile_wchodzi[i + 2][j][1][2][1][0] + ile_wchodzi[i + 1][j][2][1][1][0] + ile_wchodzi[i][j][2][0][1][0];
					sr[j] = ile_wchodzi[i + 3][j][0][2][2][2] + ile_wchodzi[i + 2][j][1][2][2][2] + ile_wchodzi[i + 1][j][2][1][2][2] + ile_wchodzi[i][j][2][0][2][2];
                    srm[j] =  ile_wchodzi[i + 3][j][0][2][1][1] + ile_wchodzi[i + 2][j][1][2][1][1] + ile_wchodzi[i + 1][j][2][1][1][1] + ile_wchodzi[i][j][2][0][1][1];
                    sama_kol[j] = ile_wchodzi[i + 3][j][0][2][0][0] + ile_wchodzi[i + 2][j][1][2][0][0] + ile_wchodzi[i + 1][j][2][1][0][0] + ile_wchodzi[i][j][2][0][0][0];
					srpref[j] = srpref[j - 1] + sr[j];
				}
				if(i2 - i > 3)
				{
					lewlew[j] = ile_wchodzi[i2][j][0][2][0][2] + ile_wchodzi[i2 - 1][j][1][2][0][2] + ile_wchodzi_pref[i2 - 2][j][2][2][0][2] - ile_wchodzi_pref[i + 1][j][2][2][0][2] + ile_wchodzi[i + 1][j][2][1][0][2] + ile_wchodzi[i][j][2][0][0][2];
					lewpraw[j] = ile_wchodzi[i2][j][0][2][1][2] + ile_wchodzi[i2 - 1][j][1][2][1][2] + ile_wchodzi_pref[i2 - 2][j][2][2][1][2] - ile_wchodzi_pref[i + 1][j][2][2][1][2] + ile_wchodzi[i + 1][j][2][1][1][2] + ile_wchodzi[i][j][2][0][1][2];
					prawlew[j] = ile_wchodzi[i2][j][0][2][2][1] + ile_wchodzi[i2 - 1][j][1][2][2][1] + ile_wchodzi_pref[i2 - 2][j][2][2][2][1] - ile_wchodzi_pref[i + 1][j][2][2][2][1] + ile_wchodzi[i + 1][j][2][1][2][1] + ile_wchodzi[i][j][2][0][2][1];
					prawpraw[j] = ile_wchodzi[i2][j][0][2][2][0] + ile_wchodzi[i2 - 1][j][1][2][2][0] + ile_wchodzi_pref[i2 - 2][j][2][2][2][0] - ile_wchodzi_pref[i + 1][j][2][2][2][0] + ile_wchodzi[i + 1][j][2][1][2][0] + ile_wchodzi[i][j][2][0][2][0];
                    lewm[j] = ile_wchodzi[i2][j][0][2][0][1] + ile_wchodzi[i2 - 1][j][1][2][0][1] + ile_wchodzi_pref[i2 - 2][j][2][2][0][1] - ile_wchodzi_pref[i + 1][j][2][2][0][1] + ile_wchodzi[i + 1][j][2][1][0][1] + ile_wchodzi[i][j][2][0][0][1];
                    prawm[j] = ile_wchodzi[i2][j][0][2][1][0] + ile_wchodzi[i2 - 1][j][1][2][1][0] + ile_wchodzi_pref[i2 - 2][j][2][2][1][0] - ile_wchodzi_pref[i + 1][j][2][2][1][0] + ile_wchodzi[i + 1][j][2][1][1][0] + ile_wchodzi[i][j][2][0][1][0];
					sr[j] = ile_wchodzi[i2][j][0][2][2][2] + ile_wchodzi[i2 - 1][j][1][2][2][2] + ile_wchodzi_pref[i2 - 2][j][2][2][2][2] - ile_wchodzi_pref[i + 1][j][2][2][2][2] + ile_wchodzi[i + 1][j][2][1][2][2] + ile_wchodzi[i][j][2][0][2][2];
                    srm[j] =  ile_wchodzi[i2][j][0][2][1][1] + ile_wchodzi[i2 - 1][j][1][2][1][1] + ile_wchodzi_pref[i2 - 2][j][2][2][1][1] - ile_wchodzi_pref[i + 1][j][2][2][1][1] + ile_wchodzi[i + 1][j][2][1][1][1] + ile_wchodzi[i][j][2][0][1][1];
                    sama_kol[j] = ile_wchodzi[i2][j][0][2][0][0] + ile_wchodzi[i2 - 1][j][1][2][0][0] + ile_wchodzi_pref[i2 - 2][j][2][2][0][0] - ile_wchodzi_pref[i + 1][j][2][2][0][0] + ile_wchodzi[i + 1][j][2][1][0][0] + ile_wchodzi[i][j][2][0][0][0];
					srpref[j] = srpref[j - 1] + sr[j];
				}
			}
			q.push(lewlew[1] + lewpraw[2] - srpref[2]);
			for(int j = 1; j <= m; j++)
			{
				if(sama_kol[j] == 1)
				{
					odp++;
				}
			}
            for(int j = 1; j <= m - 1; j++)
			{
				if(lewm[j] + prawm[j + 1] == 1)
				{
					odp++;
				}
			}
			for(int j = 1; j <= m - 2; j++)
			{
				if(lewlew[j] + srm[j + 1] + prawpraw[j + 2] == 1)
				{
					odp++;
				}
			}
			for(int j = 4; j <= m; j++)
			{
				int cur = q.front();
				q.pop();
				f[cur]++;
				cur = prawpraw[j] + prawlew[j - 1] + srpref[j - 2];
				odp += f[1 - cur];
				q.push(lewlew[j - 2] + lewpraw[j - 1] - srpref[j - 1]);
			}
		}
	}
	cout << odp << endl;
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20