Submission #1329483

#TimeUsernameProblemLanguageResultExecution timeMemory
1329483MuhammadSaramOrchard (NOI14_orchard)C++20
0 / 25
1 ms836 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 3, M = 1e6 + 1;
const int N1 = 151, M1 = 5001;

int pre[N][M], pre1[N1][M1];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int n,m,cnt=0,a;
	cin>>n>>m;
	if (n>2)
	{
		for (int i=1;i<=n;i++)
		{
			string s;
			cin>>s;
			int su=0;
			for (int j=1;j<=m;j++)
				a=s[j-1]-'0', su+=1-a*2, cnt+=a, pre1[i][j]=pre1[i-1][j]+su;
		}
		int ans=n*m;
		for (int i=0;i<n;i++)
			for (int i1=i+1;i1<=n;i1++)
			{
				int mn=0;
				for (int j=1;j<=m;j++)
					ans=min(ans,pre1[i1][j]-pre1[i][j]+mn+cnt), mn=min(mn,pre1[i][j]-pre1[i1][j]);
			}
		cout<<ans<<endl;
		return 0;
	}
	for (int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		int su=0;
		for (int j=1;j<=m;j++)
			a=s[j-1]-'0', su+=1-a*2, cnt+=a, pre[i][j]=pre[i-1][j]+su;
	}
	int ans=n*m;
	for (int i=0;i<n;i++)
		for (int i1=i+1;i1<=n;i1++)
		{
			int mn=0;
			for (int j=1;j<=m;j++)
				ans=min(ans,pre[i1][j]-pre[i][j]+mn+cnt), mn=min(mn,pre[i][j]-pre[i1][j]);
		}
	cout<<ans<<endl;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...