Submission #1330105

#TimeUsernameProblemLanguageResultExecution timeMemory
1330105secondaccountmaybeZemljište (COCI22_zemljiste)C++20
30 / 70
2095 ms4204 KiB
#include <bits/stdc++.h>
#define ll long long
#define ss string
//designed by marss
using namespace std;
void f()
{
	ll r,s,a,b;
	cin>>r>>s>>a>>b;
	vector<vector<ll>>g(r,vector<ll>(s));
	for(ll i=0;i<r;i++)
	{
		for(ll j=0;j<s;j++)
		{
			cin>>g[i][j];
		}
	}
	vector<vector<ll>>p(r+1,vector<ll>(s,0));
	for(ll i=1;i<=r;i++)
	{
		for(ll j=0;j<s;j++)
		{
			p[i][j]=p[i-1][j]+g[i-1][j];
		}
	}
	ll ans=2e18;
	for(ll r1=0;r1<r;r1++)
	{
		for(ll r2=r1;r2<r;r2++)
		{
			vector<ll>c(s);
			for(ll j=0;j<s;j++)
			{
				c[j]=p[r2+1][j]-p[r1][j];
			}
			vector<ll>q(s+1,0);
			for(ll j=0;j<s;j++)
			{
				q[j+1]=q[j]+c[j];
			}
			sort(q.begin(),q.end());
			for(ll j=0;j<=s;j++)
			{
				ll ta=q[j]-a;
				ll tb=q[j]-b;
				auto upd=[&](ll target)
				{
					auto it=lower_bound(q.begin(),q.end(),target);
					if(it!=q.end())
					{
						ll x=q[j]-(*it);
						if(x!=0)
						{
							ll d=abs(x-a)+abs(x-b);
							ans=min(ans,d);
						}
					}
					if(it!=q.begin())
					{
						--it;
						ll x=q[j]-(*it);
						if(x!=0)
						{
							ll d=abs(x-a)+abs(x-b);
							ans=min(ans,d);
						}
					}
				};
				upd(ta);
				upd(tb);
			}
		}
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll t=1;
	while(t--)
	{
		f();
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...