oj.uz

Submission #56356

# Submission time Handle Problem Language Result Execution time Memory
56356 2018-07-11T07:09:12 Z leejseo 배열 탈출 (GA8_array) C++
49 / 100
 952 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;
int A[2230][2230], D[2230][2230], N;

inline bool valid(int i, int j) {
	return 0<=i && i<N && 0<=j && j<N;
}

void input(){
	scanf("%d", &N);
	for (int i=0; i<N; i++){
		for (int j=0; j<N; j++){
			scanf("%d", &A[i][j]);
		}
	}
}

void DP(){
	D[0][0] = 0;
	for (int s=1; s<2*N-1; s++){
		for (int i=max(0, s-N+1); i<min(N, s+1); i++){
			int j = s-i;
			D[i][j] = (int)1e9;
			if (valid(i-1, j)) D[i][j] = min(D[i][j], D[i-1][j] + max(0, A[i][j] - A[i-1][j] + 1));
			if (valid(i, j-1)) D[i][j] = min(D[i][j], D[i][j-1] + max(0, A[i][j] - A[i][j-1] + 1));
		}
	}
}

int main(void){
	input();
	DP();
	printf("%d\n", D[N-1][N-1]);
}

Compilation message

array.cpp: In function 'void input()':
array.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
array.cpp:13: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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 472 KB Output is correct
4 Correct 3 ms 584 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 3 ms 736 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 880 KB Output is correct
11 Correct 3 ms 880 KB Output is correct
12 Correct 3 ms 880 KB Output is correct
13 Correct 3 ms 880 KB Output is correct
14 Correct 2 ms 880 KB Output is correct
15 Correct 3 ms 880 KB Output is correct
16 Correct 2 ms 904 KB Output is correct
17 Correct 2 ms 912 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 916 KB Output is correct
2 Correct 2 ms 924 KB Output is correct
3 Correct 2 ms 928 KB Output is correct
4 Correct 3 ms 936 KB Output is correct
5 Correct 2 ms 940 KB Output is correct
6 Correct 3 ms 944 KB Output is correct
7 Correct 2 ms 948 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 2 ms 960 KB Output is correct
11 Correct 2 ms 1004 KB Output is correct
12 Correct 3 ms 1004 KB Output is correct
13 Correct 2 ms 1004 KB Output is correct
14 Correct 3 ms 1004 KB Output is correct
15 Correct 3 ms 1004 KB Output is correct
16 Correct 3 ms 1004 KB Output is correct
17 Correct 2 ms 1004 KB Output is correct
18 Correct 2 ms 1004 KB Output is correct
19 Correct 2 ms 1004 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3468 KB Output is correct
2 Correct 11 ms 3624 KB Output is correct
3 Correct 12 ms 3832 KB Output is correct
4 Correct 11 ms 4000 KB Output is correct
5 Correct 14 ms 4300 KB Output is correct
6 Correct 10 ms 4300 KB Output is correct
7 Correct 11 ms 4536 KB Output is correct
8 Correct 10 ms 4716 KB Output is correct
9 Correct 9 ms 4752 KB Output is correct
10 Correct 9 ms 4896 KB Output is correct
11 Correct 8 ms 5048 KB Output is correct
12 Correct 10 ms 5192 KB Output is correct
13 Correct 9 ms 5340 KB Output is correct
14 Correct 12 ms 5616 KB Output is correct
15 Correct 11 ms 5788 KB Output is correct
16 Correct 11 ms 5960 KB Output is correct
17 Correct 10 ms 6112 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 60160 KB Output is correct
2 Runtime error 952 ms 66560 KB Memory limit exceeded 66560 {'time-wall': '1.016', 'max-rss': '40284', 'csw-forced': '175', 'cg-mem': '66560', 'time': '0.952', 'csw-voluntary': '5'} 65536
3 Halted 0 ms 0 KB -