oj.uz

답안 #67281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67281 2018-08-13T19:18:32 Z quoriess Maxcomp (info1cup18_maxcomp) C++14
0 / 100
 4 ms 628 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 
 * */
void rotate90(vector<vector<int> >& cevir,vector<vector<int> >& yeni){
	/*
1 4 7 8
2 5 9 *
3 6 - |
* 
* 
* 
3 2 1
6 5 4
- 9 7
| * 8 
 
 0,0 -> 0,2
 1,0 -> 0,1
 2,0 -> 0,0
 ters çevir, n-ikinci * */
	for (int i = 0; i < (int)cevir.size(); i++)
	{
		for (int j = 0; j < (int)cevir[0].size(); j++)
		{
			yeni[j][cevir.size()-i-1]=cevir[i][j];
		}
		
	}
	
}
/*
	min en sağ aşağıda olsun: 
	
	value+k.y+k.x
	* 
 * */
int ans=-1e7;
void solve(vector<vector<int> >& par){
	vector<vector<int> > dp(n,vector<int>(m,-1e4));
	dp[0][0]=par[0][0];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if(i!=0)dp[i][j]=max(dp[i][j],dp[i-1][j]);
			
			if(j!=0)dp[i][j]=max(dp[i][j],dp[i][j-1]);
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			ans=max(ans,dp[i][j]-par[i][j]-i-j);
			//cout << ans<<"\n";
			//ans=max(ans,0);
		}
	}
}
void yazdir(vector<vector<int> > matris){
	for (int i = 0; i < (int) matris.size(); i++)
	{
		for (int j = 0; j<(int) matris[0].size()  ; j++)
		{
			cout<<matris[i][j]<<" ";
		}
		cout <<"\n";
	}
	
}
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];
		}
	}
	
	vector<vector<int> > eski,yeni;
	eski=matris;
	for (int i = 0; i < 4; i++)
	{
		solve(eski);
		//cout <<"\n";
		//yazdir(eski);
		yeni=vector<vector<int> >(eski[0].size(),vector<int>(eski.size()));
		rotate90(eski,yeni);
		//yazdir(yeni);
		eski=yeni;
	}
	printf("%d",ans);
	return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -