Submission #67405

#	Time	Username	Problem	Language	Result	Execution time	Memory
67405		quoriess	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	356 ms	47136 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
	max-min-(-max.x+-max.y+min.x+min.y+1)
	*
 * */
int ans=-1e7;
void solve(vector<vector<int> >& par){
    vector<vector<int> > dp(par.size(),vector<int>(par[0].size(),-1e6));
	for (int i = 0; i < par.size(); i++)
	{
		for (int j = 0; j < par[0].size(); j++)
		{
			dp[i][j]=max(dp[i][j],par[i][j]+i+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 < par.size(); i++)
	{
		for (int j = 0; j < par[0].size(); j++)
		{
			ans=max(ans,dp[i][j]-par[i][j]-i-j-1);
			//cout << ans<<"\n";
		}
	}
}
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";
	}
}
/*
4 5
8 7 6 9 16
3 12 19 33 21
9 9 9 9 9
15 14 13 11 17

1 4
2 4


 * */
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++)
		{
			scanf("%d",&matris[i][j]);
		}
	}

	vector<vector<int> > eski,yeni,yeni2,yeni3;
	for(int i=0;i<n;i++){
        eski.push_back(vector<int>());
        for(int j=0;j<m;j++){
            eski[i].push_back(matris[i][j]);
        }
	}
	solve(matris);
	yeni=vector<vector<int> >(matris[0].size(),vector<int>(matris.size()));
	rotate90(matris,yeni);
	solve(yeni);
	yeni2=vector<vector<int> >(yeni[0].size(),vector<int>(yeni.size()));
	rotate90(yeni,yeni2);
	solve(yeni2);
	yeni3=vector<vector<int> >(yeni2[0].size(),vector<int>(yeni2.size()));
	rotate90(yeni2,yeni3);
	solve(yeni3);
	/*for (int i = 0; i < 4; i++)
	{
		//cout <<"iter: "<<i<<"\n";
		solve(eski);
		//cout << "ans: "<<ans<<" ";
		//cout <<"\n";
		//yazdir(eski);
		rotate90(eski,yeni);
		//yazdir(yeni);
		eski=yeni;
	}*/
	cout <<ans<<"\n";
	return 0;
}

Compilation message (stderr)

maxcomp.cpp: In function 'void solve(std::vector<std::vector<int> >&)':
maxcomp.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < par.size(); i++)
                  ~~^~~~~~~~~~~~
maxcomp.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < par[0].size(); j++)
                   ~~^~~~~~~~~~~~~~~
maxcomp.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < par.size(); i++)
                  ~~^~~~~~~~~~~~
maxcomp.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < par[0].size(); j++)
                   ~~^~~~~~~~~~~~~~~
maxcomp.cpp: In function 'int main()':
maxcomp.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&matris[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

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