oj.uz

Submission #28679

# Submission time Handle Problem Language Result Execution time Memory
28679 2017-07-16T08:39:23 Z Sorry AcornCkiGuiziTeam(#1226, gs13068) Test Data Creation (FXCUP2_testdata) C++14
0 / 1
 249 ms 110488 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

int a[90009];
int b[90009];
int d[303][303][303];

int main() {
	int ti, tj;
	int i, j, k, l, m, n, t;
	scanf("%d%d", &m, &n);
	for (i = 0; i < n * m; i++) scanf("%d", &a[i]);
	for (i = 0; i < n; i++) for (j = 0; j < m; j++) for (k = 0; k <= 300; k++) d[i][j][k] = 2e9;
	d[0][0][0] = 0;
	for (i = 0; i < n; i++) for (j = 0; j < m; j++) for (k = 0; k <= 300; k++) {
		t = i * m + j + k;
		ti = t / n;
		tj = t % n;
		if (k) t = d[i][j][k] + a[i * m + j];
		else t = d[i][j][k];
		if (i + 1 < n && k >= m) d[i + 1][j][k - m] = min(d[i + 1][j][k - m], t);
		if (j + 1 < m && k) d[i][j + 1][k - 1] = min(d[i][j + 1][k - 1], t);
		if (k) t = d[i][j][k] + a[ti * n + tj];
		else t = d[i][j][k];
		if (ti + 1 < m && k + n <= 300) d[i][j][k + n] = min(d[i][j][k + n], t);
		if (tj + 1 < n && k + 1 <= 300) d[i][j][k + 1] = min(d[i][j][k + 1], t);
	}
	printf("%d\n", d[n - 1][m - 1][0] + a[n * m - 1]);
	i = n - 1;
	j = m - 1;
	k = 0;
	while (i || j || k) {
		t = i * m + j + k;
		ti = t / n;
		tj = t % n;
		b[i * m + j] = b[ti * n + tj] = 1;
		if (i && k + m <= 300 && d[i][j][k] == d[i - 1][j][k + m] + a[i * m + j - m]) {
			i--;
			k += m;
			continue;
		}
		if (j && k + 1 <= 300 && d[i][j][k] == d[i][j - 1][k + 1] + a[i * m + j - 1]) {
			j--;
			k++;
			continue;
		}
		if (ti && k - n >= 0 && d[i][j][k] == d[i][j][k - n] + (k - n ? a[t - n] : 0)) {
			k -= n;
			continue;
		}
		k--;
	}
	b[0] = 1;
	for (i = 0; i < n; i++, puts("")) for (j = 0; j < m; j++) printf("%d ", b[i * m + j]);
	return 0;
}

Compilation message

testdata.cpp: In function 'int main()':
testdata.cpp:12:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l, m, n, t;
               ^
testdata.cpp:13:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &m, &n);
                       ^
testdata.cpp:14:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n * m; i++) scanf("%d", &a[i]);
                                                ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 110488 KB Correct
2 Correct 0 ms 110488 KB Correct
3 Correct 0 ms 110488 KB Correct
4 Correct 9 ms 110488 KB Correct
5 Correct 63 ms 110488 KB Correct
6 Correct 246 ms 110488 KB Correct
7 Correct 249 ms 110488 KB Correct
8 Correct 0 ms 110488 KB Correct
9 Correct 0 ms 110488 KB Correct
10 Correct 0 ms 110488 KB Correct
11 Correct 0 ms 110488 KB Correct
12 Correct 3 ms 110488 KB Correct
13 Correct 3 ms 110488 KB Correct
14 Correct 6 ms 110488 KB Correct
15 Correct 19 ms 110488 KB Correct
16 Correct 63 ms 110488 KB Correct
17 Incorrect 99 ms 110488 KB Wrong
18 Halted 0 ms 0 KB -