oj.uz

Submission #56357

# Submission time Handle Problem Language Result Execution time Memory
56357 2018-07-11T07:09:54 Z leejseo 배열 탈출 (GA8_array) C++17
49 / 100
 1126 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 376 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 3 ms 748 KB Output is correct
15 Correct 3 ms 748 KB Output is correct
16 Correct 3 ms 916 KB Output is correct
17 Correct 2 ms 916 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 3 ms 916 KB Output is correct
3 Correct 2 ms 916 KB Output is correct
4 Correct 3 ms 916 KB Output is correct
5 Correct 2 ms 916 KB Output is correct
6 Correct 3 ms 916 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 2 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct
10 Correct 3 ms 916 KB Output is correct
11 Correct 3 ms 916 KB Output is correct
12 Correct 3 ms 916 KB Output is correct
13 Correct 3 ms 916 KB Output is correct
14 Correct 2 ms 916 KB Output is correct
15 Correct 2 ms 916 KB Output is correct
16 Correct 3 ms 916 KB Output is correct
17 Correct 3 ms 916 KB Output is correct
18 Correct 3 ms 916 KB Output is correct
19 Correct 3 ms 916 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3084 KB Output is correct
2 Correct 13 ms 3256 KB Output is correct
3 Correct 17 ms 3428 KB Output is correct
4 Correct 11 ms 3600 KB Output is correct
5 Correct 13 ms 3772 KB Output is correct
6 Correct 17 ms 3908 KB Output is correct
7 Correct 12 ms 4116 KB Output is correct
8 Correct 15 ms 4288 KB Output is correct
9 Correct 16 ms 4460 KB Output is correct
10 Correct 21 ms 4476 KB Output is correct
11 Correct 16 ms 4628 KB Output is correct
12 Correct 15 ms 4776 KB Output is correct
13 Correct 17 ms 5056 KB Output is correct
14 Correct 15 ms 5200 KB Output is correct
15 Correct 18 ms 5372 KB Output is correct
16 Correct 17 ms 5548 KB Output is correct
17 Correct 25 ms 5716 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 49852 KB Output is correct
2 Correct 967 ms 49852 KB Output is correct
3 Runtime error 987 ms 66560 KB Memory limit exceeded 66560 {'time-wall': '1.093', 'max-rss': '40280', 'csw-forced': '205', 'cg-mem': '66560', 'time': '0.987', 'csw-voluntary': '7'} 65536
4 Halted 0 ms 0 KB -