Submission #1036184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036184		vjudge1	Zemljište (COCI22_zemljiste)	C++17	70 / 70	1691 ms	4700 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 501;

int pre[M][M];

signed main()
{
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	if (a>b)
		swap(a,b);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			int x;
			cin>>x;
			pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+x;
		}
	int val1=1e18,val2=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			for (int j1=j-1;j1>=0;j1--)
			{
				int s=0,e=i,su;
				while (s+1<e)
				{
					int mid=(s+e)/2;
					su=pre[i][j]-pre[i][j1]-pre[mid][j]+pre[mid][j1];
					if (su>=a)
						s=mid;
					else
						e=mid;
				}
				su=pre[i][j]-pre[i][j1]-pre[s][j]+pre[s][j1];
				if (su>=a)
					val1=min(val1,su);
				s=-1,e=i-1;
				while (s+1<e)
				{
					int mid=(s+e)/2;
					su=pre[i][j]-pre[i][j1]-pre[mid][j]+pre[mid][j1];
					if (su<a)
						e=mid;
					else
						s=mid;
				}
				su=pre[i][j]-pre[i][j1]-pre[e][j]+pre[e][j1];
				if (su<a)
					val2=max(val2,su);
			}
		}
	cout<<min(abs(val1-a)+abs(val1-b),abs(val2-a)+abs(val2-b))<<endl;
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40