oj.uz

Submission #66996

# Submission time Handle Problem Language Result Execution time Memory
66996 2018-08-13T07:44:19 Z hamzqq9 Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 267 ms 67588 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2000000000
#define MOD 1000000007
#define N 1005
#define MAX 10000006
#define LOG 22
using namespace std;

int n,m,a[N][N],p1[N][N];
int ans=-inf;
int add[4][2]={-1,-1,-1,1,1,-1,1,1};

void check(int cur) {

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			umax(ans,a[i][j]+p1[i][j]+add[cur][0]*i+add[cur][1]*j-1);

		}

	}

}

int main() {
 
//	freopen("input.txt","r",stdin);
 
	scanf("%d %d",&n,&m);

	for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++) p1[i][j]=-inf;

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			scanf("%d",&a[i][j]);

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			p1[i][j]=-inf;

			umax(p1[i][j],max(p1[i-1][j],p1[i][j-1]));
			umax(p1[i][j],-a[i][j]+i+j);

		}

	}

	check(0);

	//printf("Cur ans-->%d\n",ans);

	for(int i=1;i<=n;i++) {

		for(int j=m;j>=1;j--) {

			p1[i][j]=-inf;

			umax(p1[i][j],max(p1[i-1][j],p1[i][j+1]));
			umax(p1[i][j],-a[i][j]+i-j);

		}

	} 

	check(1);

//	printf("Cur ans-->%d\n",ans);
	for(int i=n;i>=1;i--) {

		for(int j=1;j<=m;j++) {

			p1[i][j]=-inf;

			umax(p1[i][j],max(p1[i+1][j],p1[i][j-1]));
			umax(p1[i][j],-a[i][j]-i+j);

		}

	}

	check(2);

//	printf("Cur ans-->%d\n",ans);
	for(int i=n;i>=1;i--) {

		for(int j=m;j>=1;j--) {

			p1[i][j]=-inf;

			umax(p1[i][j],max(p1[i+1][j],p1[i][j+1]));
			umax(p1[i][j],-a[i][j]-i-j);

		}

	}

	check(3);
//	printf("Cur ans-->%d\n",ans);

	printf("%d",ans);

}

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
maxcomp.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][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 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 3 ms 544 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 648 KB Output is correct
2 Correct 2 ms 648 KB Output is correct
3 Correct 2 ms 648 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 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 3 ms 928 KB Output is correct
10 Correct 3 ms 928 KB Output is correct
11 Correct 3 ms 928 KB Output is correct
12 Correct 4 ms 928 KB Output is correct
13 Correct 3 ms 928 KB Output is correct
14 Correct 2 ms 932 KB Output is correct

Subtask #4
40.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 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 2 ms 648 KB Output is correct
11 Correct 2 ms 648 KB Output is correct
12 Correct 3 ms 928 KB Output is correct
13 Correct 3 ms 928 KB Output is correct
14 Correct 3 ms 928 KB Output is correct
15 Correct 4 ms 928 KB Output is correct
16 Correct 3 ms 928 KB Output is correct
17 Correct 2 ms 932 KB Output is correct
18 Correct 218 ms 16416 KB Output is correct
19 Correct 238 ms 24848 KB Output is correct
20 Correct 222 ms 33036 KB Output is correct
21 Correct 267 ms 41676 KB Output is correct
22 Correct 243 ms 50228 KB Output is correct
23 Correct 237 ms 58764 KB Output is correct
24 Correct 207 ms 67588 KB Output is correct