oj.uz

Submission #67103

# Submission time Handle Problem Language Result Execution time Memory
67103 2018-08-13T10:41:24 Z quoriess Maxcomp (info1cup18_maxcomp) C++14
15 / 100
 148 ms 476 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
vector<vector<int> > matris;
int n,m;
typedef pair<lli,pii> data;
const int MAXN=1e3+5, MAXM=1e3+5;

vector<pii> komsu(int a,int b){
	vector<pii> don;
	for (int i = -1; i < 2; i++)
	{
		for (int j = -1; j < 2; j++)
		{
			if(a+i>=0 && a+i< n && b+j<m && b+j>=0 && (i!=0||j!=0) && (i==0 || j==0)){
				don.push_back({a+i,b+j});
			}
		}
	}
	return don;
}
/*
3 3
1 7 5
3 6 9
4 8 3 
 * */
int maxsegmentTree[4*MAXM],minsegmentTree[4*MAXM];
void buildTreex(int node,int a,int b){
	if(a==b)maxsegmentTree[node]=matris[0][a];
	else
	{
		buildTreex(node*2,a,(a+b)/2);
		buildTreex(node*2+1,(a+b)/2+1,b);
		maxsegmentTree[node]=max(maxsegmentTree[node*2],maxsegmentTree[node*2+1]);
	}
}
int queryTreex(int node,int a,int b,int l,int r){
	if(a>b||a>r||b<l)return 0;
	if(a>=l&&b<=r)return maxsegmentTree[node];
	int q1=queryTreex(node*2,a,(a+b)/2,l,r);
	int q2=queryTreex(node*2+1,(a+b)/2+1,b,l,r);
	return max(q1,q2);
}
void buildTreen(int node,int a,int b){
	if(a==b)minsegmentTree[node]=matris[0][a];
	else
	{
		buildTreen(node*2,a,(a+b)/2);
		buildTreen(node*2+1,(a+b)/2+1,b);
		minsegmentTree[node]=min(minsegmentTree[node*2],minsegmentTree[node*2+1]);
	}
	//cout << "built: "<<a<<"-"<<b<<" : "<<minsegmentTree[node]<<"\n";
}
int queryTreen(int node,int a,int b,int l,int r){
	if(a>b||a>r||b<l)return 1e9+7;
	if(a>=l&&b<=r)return minsegmentTree[node];
	int q1=queryTreen(node*2,a,(a+b)/2,l,r);
	int q2=queryTreen(node*2+1,(a+b)/2+1,b,l,r);
	
	return min(q1,q2);
}
/*
1 6
10 6 3 7 1 1
-1
 
 * */
int main(){
	cin>>n>>m;
	matris=vector<vector<int> >(n,vector<int>(m,0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin>>matris[i][j];
		}
	}
	if(n==1){
		int ans=-1e7;
		buildTreen(1,0,m-1);
		buildTreex(1,0,m-1);
		
		for (int i = 0; i < m; i++)
		{
			for (int j = i; j < m; j++)
			{
				int maxi=queryTreex(1,0,n*m-1,i,j);
				int mini=queryTreen(1,0,n*m-1,i,j);
				//cout << "i: "<<i<<" j: "<<j<<" maxi: "<< maxi<<" mini: "<<mini<<"\n";
				ans=max(ans,maxi-mini-(j-i+1));
			}
			
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 356 KB Output is correct
2 Correct 146 ms 392 KB Output is correct
3 Correct 142 ms 476 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -