Submission #1127647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127647		xanlar2009	Maxcomp (info1cup18_maxcomp)	C++20	15 / 100	58 ms	484 KiB

maxcomp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define run  ios_base::sync_with_stdio(false);cin.tie(0);

#define ln length()
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned ll
#define ld double
#define endl "\n"
#define pb push_back
#define fi first
#define se second
 
#define pi acos(-1)
#define N 1007
#define INF 10000000000
#define minimum -9223372036854775807
#define maximum -minimum
#define mod 1000000007
 
using namespace std;
using namespace __gnu_pbds;
template <class t>
using ordered_set=tree<t, null_type,less_equal<t>, rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll gcd(ll a, ll b)
{
	if(b==0)
		return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b)
{
	return a/gcd(a, b)*b;
}

bool isprime(ll n)
{
	if(n==1)
		return 0;
	for(ll i=2; i*i<=n; i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}

ll binpow(ll a, ll b)
{
    a%=mod;
    ll res=1;
    while(b>0)
	{
        if(b%2==1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}

ll n, m;
ll a[N][N];
pll t[N];

void build(ll node, ll l, ll r)
{
	if(l==r)
	{
		t[node].first=a[1][l];
		t[node].second=a[1][l];
		return;
	}
	ll mid=(l+r)/2;
	build(node*2, l, mid);
	build(node*2+1, mid+1, r);
	t[node].first=min(t[node*2].first, t[node*2+1].first);
	t[node].second=max(t[node*2].second, t[node*2+1].second);
}

pll get(ll node, ll l, ll r, ll ql, ll qr)
{
	if(qr<l || r<ql)
		return {maximum, minimum};
	if(ql<=l && r<=qr)
		return t[node];
	ll mid=(l+r)/2;
	pll res1=get(node*2, l, mid, ql, qr);
	pll res2=get(node*2+1, mid+1, r, ql, qr);
	return {min(res1.first, res2.first), max(res1.second, res2.second)};
}

int main()
{
	run;
	cin>>n>>m;
	for(ll i=1; i<=n; i++)
	{
		for(ll j=1; j<=m; j++)
		{
			cin>>a[i][j];
		}
	}
	ll cvb=0;
	if(n==1)
	{
		build(1, 1, m);
		for(ll i=1; i<=m; i++)
		{
			for(ll j=i; j<=m; j++)
			{
				pll res=get(1, 1, m, i, j);
				if(cvb<res.second-res.first-(j-i+1))
				{
					cvb=max(cvb, res.second-res.first-(j-i+1));
//					cout<<i<<" "<<j<<endl;
				}
				
			}
		}
		cout<<cvb<<endl;
	}
	else
	{
		ll sz=n*m;
		vector<ll>v(sz+1, 0);
		ll idx=1;
		for(ll i=1; i<=n; i++)
		{
			for(ll j=1; j<=m; j++)
			{
				v[idx]=a[i][j];
				idx++;
			}
		}
		for(ll mask=0; mask<(1<<sz); mask++)
		{
			ll num=0, minn=maximum, maxx=minimum;
			for(ll i=1; i<=sz; i++)
			{
				if((1<<mask)&i)
				{
					num++;
					minn=min(minn, v[i]);
					maxx=max(maxx, v[i]);
				}
			}
			cvb=max(cvb, maxx-minn-num);	
		}
		cout<<cvb<<endl;
	}
}
// By Xanlar

• Subtask 1: 0 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40