Submission #67281

#	Time	Username	Problem	Language	Result	Execution time	Memory
67281		quoriess	Maxcomp (info1cup18_maxcomp)	C++14	0 / 100	4 ms	628 KiB

maxcomp

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40