Submission #28679

#	Time	Username	Problem	Language	Result	Execution time	Memory
28679		Sorry AcornCkiGuiziTeam (#68)	Test Data Creation (FXCUP2_testdata)	C++14	0 / 1	249 ms	110488 KiB

testdata

#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 (stderr)

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