제출 #1329488

#제출 시각아이디문제언어결과실행 시간메모리
1329488MuhammadSaram과수원 (NOI14_orchard)C++20
25 / 25
100 ms4260 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], cnt;

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

	int n,m,a;
	cin>>n>>m;
	if (n>2)
	{
		for (int i=1;i<=n;i++)
		{
			int su=0;
			for (int j=1;j<=m;j++)
				cin>>a, 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++)
	{
		int su=0;
		for (int j=1;j<=m;j++)
			cin>>a, 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...