oj.uz

Submission #1003270

# Submission time Handle Problem Language Result Execution time Memory
1003270 2024-06-20T08:23:25 Z ulianamalanyak Dijamant (COCI22_dijamant) C++14
70 / 70
 201 ms 51284 KB 
#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define INF 1000000000000

typedef int ll;

const int DIM=2e3+7;

ll n,m;
int a[DIM][DIM];
int dp1[DIM][DIM];
int dp2[DIM][DIM];

int main()
{
    //freopen ("input.txt","r",stdin);
    //freopen ("output.txt","w",stdout);
    
    cin >> n >> m;

	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			char c;
			cin >> c;
			if (c=='#') a[i][j]=1;
		}
	}

	for (int i=1;i<=n;i++)
	{
		int cur=-1;
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]==0) dp1[i][j]=-1;
			else
			{
				if (cur==-1) 
				{
					dp1[i][j]=j;
				}
				else if (cur==j-1)
				{
					dp1[i][j]=j;
				}
				else
				{
					if (dp1[i-1][j-1]==cur+1||(j-1==cur+1&&a[i-1][j-1]))
					{
						dp1[i][j]=cur;
					}
					else dp1[i][j]=j;
				}

				cur=j;
			}
		}
	}

	for (int i=n;i>=1;i--)
	{
		int cur=-1;
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]==0) dp2[i][j]=-1;
			else
			{
				if (cur==-1) 
				{
					dp2[i][j]=j;
				}
				else if (cur==j-1)
				{
					dp2[i][j]=j;
				}
				else
				{
					if (dp2[i+1][j-1]==cur+1||(j-1==cur+1&&a[i+1][j-1]))
					{
						dp2[i][j]=cur;
					}
					else dp2[i][j]=j;
				}

				cur=j;
			}
		}
	}

	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			//cout << i << " " << j << " " << dp1[i][j] << " " << dp2[i][j] << endl;
		}
	}

	ll count=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]&&dp1[i][j]!=j&&dp2[i][j]!=j&&dp1[i][j]==dp2[i][j]) 
			{
				count++;
				//cout << i << " " << dp1[i][j] << " " << j << endl;
			}
		}
	}

	cout << count << endl;
  
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 114 ms 33952 KB Output is correct
15 Correct 113 ms 48280 KB Output is correct
16 Correct 201 ms 48212 KB Output is correct
17 Correct 134 ms 48724 KB Output is correct
18 Correct 163 ms 51284 KB Output is correct
19 Correct 154 ms 46928 KB Output is correct
20 Correct 131 ms 50772 KB Output is correct
21 Correct 112 ms 46248 KB Output is correct
22 Correct 146 ms 50400 KB Output is correct
23 Correct 154 ms 46160 KB Output is correct
24 Correct 144 ms 50000 KB Output is correct
25 Correct 107 ms 34896 KB Output is correct
26 Correct 115 ms 46932 KB Output is correct