Submission #635842

#	Time	Username	Problem	Language	Result	Execution time	Memory
635842		kabika	Maxcomp (info1cup18_maxcomp)	C++17	0 / 100	1 ms	340 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll MOD = 1e9 + 7;
#define pb push_back
#define pli pair<ll,int>
#define pr make_pair
#define ft first
#define sd second
#define grid n,vector<ll>(m,0)

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<ll>> v(grid);
	for(int i = 0; i < n; ++i)
	{
	    for(int j = 0; j < m; ++j)
	        cin >> v[i][j];
	}
	vector<vector<ll>> dp(grid), mx(grid), mn(grid), s(grid);
	dp[0][0] = -1;
	mx[0][0] = mn[0][0] = v[0][0];
	s[0][0] = 1;
	for(int i = 0; i < n; ++i)
	{
	    for(int j = 0; j < m; ++j)
	    {
	        if(i == 0 && j == 0)
	            continue;
	        
	        if(i == 0)
	        {
	            mx[i][j] = max(mx[i][j-1],v[i][j]);
	            mn[i][j] = min(mn[i][j-1],v[i][j]);
	            s[i][j] = s[i][j-1]+1;
	            dp[i][j] = mx[i][j]-mn[i][j]-s[i][j];
	            if(dp[i][j] < -1)
	            {
	                dp[i][j] = -1;
	                mx[i][j] = mn[i][j] = v[i][j];
	                s[i][j] = 1;
	            }
	            continue;
	        }
	        
	        if(j == 0)
	        {
	            mx[i][j] = max(mx[i-1][j],v[i][j]);
	            mn[i][j] = min(mn[i-1][j],v[i][j]);
	            s[i][j] = s[i-1][j]+1;
	            dp[i][j] = mx[i][j]-mn[i][j]-s[i][j];
	            if(dp[i][j] <= -1)
	            {
	                dp[i][j] = -1;
	                mx[i][j] = mn[i][j] = v[i][j];
	                s[i][j] = 1;
	            }
	            continue;
	        }
	        
	        ll tj = max(mx[i][j-1],v[i][j])-min(mn[i][j-1],v[i][j])-s[i][j-1]-1;
	        ll ti = max(mx[i-1][j],v[i][j])-min(mn[i-1][j],v[i][j])-s[i-1][j]-1;
	        if(ti <= -1 && tj <= -1)
	        {
	            dp[i][j] = -1;
	            mx[i][j] = mn[i][j] = v[i][j];
	            s[i][j] = 1;
	            continue;
	        }
	        if(ti < tj)
	        {
	            dp[i][j] = tj;
	            mx[i][j] = max(mx[i][j-1],v[i][j]);
	            mn[i][j] = min(mn[i][j-1],v[i][j]);
	            s[i][j] = s[i][j-1]+1;
	            continue;
	        }
	        dp[i][j] = ti;
	        mx[i][j] = max(mx[i-1][j],v[i][j]);
	        mn[i][j] = min(mn[i-1][j],v[i][j]);
	        s[i][j] = s[i-1][j]+1;
	    }
	}
	
	ll ans = -(1e9+7);
	for(int i = 0; i < n; ++i)
	    ans = max(ans,*max_element(dp[i].begin(),dp[i].end()));
	cout << ans << '\n';
	return 0;
}

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