oj.uz

Submission #67013

# Submission time Handle Problem Language Result Execution time Memory
67013 2018-08-13T08:16:47 Z ekrem Maxcomp (info1cup18_maxcomp) C++
100 / 100
 474 ms 36280 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 2000000007
#define N 1005
using namespace std;

int n, m, ans = -inf, a[N][N], dp[2][4][N][N];
int o[] = {-1, 0, 1, 0};
int p[] = {0, 1, 0, -1};

int f(int dur, int yon, int i, int j){
	int &r = dp[dur][yon][i][j];
	if(r != -inf)
		return r;
	if(i < 1 or j < 1 or i > n or j > m)
		return -inf + 1;
	if(dur == 0){
		if(a[i][j] > f(dur, yon, i + o[yon], j + p[yon]) - 1)
			r = a[i][j];
		else
			r = f(dur, yon, i + o[yon], j + p[yon]) - 1;
	}
	if(dur == 1){
		if(-a[i][j] > f(dur, yon, i + o[yon], j + p[yon]) - 1)
			r = -a[i][j];
		else
			r = f(dur, yon, i + o[yon], j + p[yon]) - 1;
	}
	return r;
}

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

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%d",&a[i][j]);
	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= m + 1; j++)
			for(int yon = 0; yon <= 3; yon++)
				for(int dur = 0; dur <= 1; dur++)
					dp[dur][yon][i][j] = -inf;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			for(int yon = 0; yon <= 3; yon++)
				for(int dur = 0; dur <= 1; dur++)
					f(dur, yon, i, j);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			for(int l = 0; l <= 3; l++)
				for(int k = 0; k <= 3; k++)
					if(l != k)
						ans = max(ans, dp[0][l][i][j] + dp[1][k][i][j] - 1 );

	printf("%d\n",ans);
	return 0;
}

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:38: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:42: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 2 ms 504 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 3 ms 740 KB Output is correct
5 Correct 2 ms 740 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 2 ms 740 KB Output is correct
8 Correct 2 ms 824 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 3 ms 740 KB Output is correct
5 Correct 2 ms 740 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 2 ms 740 KB Output is correct
8 Correct 2 ms 824 KB Output is correct
9 Correct 5 ms 2404 KB Output is correct
10 Correct 4 ms 2404 KB Output is correct
11 Correct 4 ms 2532 KB Output is correct
12 Correct 4 ms 2532 KB Output is correct
13 Correct 5 ms 2532 KB Output is correct
14 Correct 5 ms 2532 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 3 ms 740 KB Output is correct
5 Correct 2 ms 740 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 2 ms 740 KB Output is correct
8 Correct 2 ms 824 KB Output is correct
9 Correct 2 ms 824 KB Output is correct
10 Correct 2 ms 824 KB Output is correct
11 Correct 3 ms 824 KB Output is correct
12 Correct 5 ms 2404 KB Output is correct
13 Correct 4 ms 2404 KB Output is correct
14 Correct 4 ms 2532 KB Output is correct
15 Correct 4 ms 2532 KB Output is correct
16 Correct 5 ms 2532 KB Output is correct
17 Correct 5 ms 2532 KB Output is correct
18 Correct 462 ms 36176 KB Output is correct
19 Correct 438 ms 36176 KB Output is correct
20 Correct 437 ms 36204 KB Output is correct
21 Correct 474 ms 36280 KB Output is correct
22 Correct 446 ms 36280 KB Output is correct
23 Correct 445 ms 36280 KB Output is correct
24 Correct 384 ms 36280 KB Output is correct