oj.uz

Submission #67006

# Submission time Handle Problem Language Result Execution time Memory
67006 2018-08-13T08:05:35 Z ekrem Maxcomp (info1cup18_maxcomp) C++
60 / 100
 500 ms 36340 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[N][N][4][2];
int o[] = {-1, 0, 1, 0};
int p[] = {0, 1, 0, -1};

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

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof dp);
	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 = 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, f(i, j, l, 0) + f(i, j, k, 1) - 1 );
					}

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

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:39: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 24 ms 31864 KB Output is correct
2 Correct 27 ms 32100 KB Output is correct
3 Correct 27 ms 32100 KB Output is correct
4 Correct 26 ms 32100 KB Output is correct
5 Correct 25 ms 32228 KB Output is correct
6 Correct 26 ms 32228 KB Output is correct
7 Correct 26 ms 32256 KB Output is correct
8 Correct 28 ms 32256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32340 KB Output is correct
2 Correct 28 ms 32340 KB Output is correct
3 Correct 29 ms 32340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31864 KB Output is correct
2 Correct 27 ms 32100 KB Output is correct
3 Correct 27 ms 32100 KB Output is correct
4 Correct 26 ms 32100 KB Output is correct
5 Correct 25 ms 32228 KB Output is correct
6 Correct 26 ms 32228 KB Output is correct
7 Correct 26 ms 32256 KB Output is correct
8 Correct 28 ms 32256 KB Output is correct
9 Correct 31 ms 32380 KB Output is correct
10 Correct 33 ms 32380 KB Output is correct
11 Correct 33 ms 32380 KB Output is correct
12 Correct 31 ms 32380 KB Output is correct
13 Correct 31 ms 32440 KB Output is correct
14 Correct 29 ms 32440 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31864 KB Output is correct
2 Correct 27 ms 32100 KB Output is correct
3 Correct 27 ms 32100 KB Output is correct
4 Correct 26 ms 32100 KB Output is correct
5 Correct 25 ms 32228 KB Output is correct
6 Correct 26 ms 32228 KB Output is correct
7 Correct 26 ms 32256 KB Output is correct
8 Correct 28 ms 32256 KB Output is correct
9 Correct 25 ms 32340 KB Output is correct
10 Correct 28 ms 32340 KB Output is correct
11 Correct 29 ms 32340 KB Output is correct
12 Correct 31 ms 32380 KB Output is correct
13 Correct 33 ms 32380 KB Output is correct
14 Correct 33 ms 32380 KB Output is correct
15 Correct 31 ms 32380 KB Output is correct
16 Correct 31 ms 32440 KB Output is correct
17 Correct 29 ms 32440 KB Output is correct
18 Execution timed out 532 ms 36340 KB Time limit exceeded
19 Halted 0 ms 0 KB -