oj.uz

Submission #67404

# Submission time Handle Problem Language Result Execution time Memory
67404 2018-08-14T08:16:13 Z quoriess Maxcomp (info1cup18_maxcomp) C++14
60 / 100
 500 ms 24444 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
	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++)
		{
			cin>>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

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++)
                   ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 412 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 3 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 3 ms 720 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 412 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 720 KB Output is correct
10 Correct 3 ms 720 KB Output is correct
11 Correct 4 ms 720 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 4 ms 720 KB Output is correct
14 Correct 4 ms 720 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 412 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 3 ms 720 KB Output is correct
11 Correct 3 ms 720 KB Output is correct
12 Correct 3 ms 720 KB Output is correct
13 Correct 3 ms 720 KB Output is correct
14 Correct 4 ms 720 KB Output is correct
15 Correct 4 ms 720 KB Output is correct
16 Correct 4 ms 720 KB Output is correct
17 Correct 4 ms 720 KB Output is correct
18 Execution timed out 613 ms 24444 KB Time limit exceeded
19 Halted 0 ms 0 KB -