oj.uz

Submission #74349

# Submission time Handle Problem Language Result Execution time Memory
74349 2018-08-31T10:57:37 Z khsoo01 Test Data Creation (FXCUP2_testdata) C++11
1 / 1
 975 ms 217728 KB 
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9, B = 301;
 
int n, m, a[90001], ans[90001], dt[90001][605];
bool f;
 
bool valid (int X, int Y) {
	if(!(1 <= X && X <= n*m && B-n <= Y && Y <= B+n)) return false;
	if(!(1 <= X+Y-B && X+Y-B <= n*m)) return false;
	return true;
}
 
void track (int X, int Y) {
	ans[X] = 1; ans[X+Y-B] = 1;
	if(X == 1 && Y == B) return;
	int i, j;
	i = X - n, j = Y + n;
	if(valid(i, j) && i+n <= n*m && j-n >= B-n && dt[i][j] + (j-n != B)*a[i+n] == dt[X][Y]) {
		track(i, j); return;
	}
	i = X - 1, j = Y + 1;
	if(valid(i, j) && i%n && j-1 >= B-n && dt[i][j] + (j-1 != B)*a[i+1] == dt[X][Y]) {
		track(i, j); return;
	}
	i = X, j = Y-m;
	if(valid(i, j) && j+m <= B+n && i+j+m-B <= n*m && dt[i][j] + (j+m != B)*a[i+j+m-B] == dt[X][Y]) {
		track(i, j); return;
	}
	i = X, j = Y-1;
	if(valid(i, j) && j+1 <= B+n && (i+j-B)%m && dt[i][j] + (j+1 != B)*a[i+j+1-B] == dt[X][Y]) {
		track(i, j); return;
	}
}
 
int main()
{
	scanf("%d%d",&n,&m);
	if(n < m) {swap(n, m); f = true;}
	for(int i=1;i<=n*m;i++) {
		scanf("%d",&a[i]);
		for(int j=B-n-1;j<=B+n+1;j++) {
			dt[i][j] = inf;
		}
	}
	dt[1][B] = a[1];
	for(int i=1;i<=n*m;i++) {
		for(int j=B-n;j<=B+n;j++) {
			if(i+j-B < 1 || i+j-B > n*m) continue;
			if(i+n <= n*m && j-n >= B-n) {
				dt[i+n][j-n] = min(dt[i+n][j-n], dt[i][j] + (j-n != B)*a[i+n]);
			}
			if(i%n && j-1 >= B-n) {
				dt[i+1][j-1] = min(dt[i+1][j-1], dt[i][j] + (j-1 != B)*a[i+1]);
			}
			if(j+m <= B+n && i+j+m-B <= n*m) {
				dt[i][j+m] = min(dt[i][j+m], dt[i][j] + (j+m != B)*a[i+j+m-B]);
			}
			if(j+1 <= B+n && (i+j-B)%m) {
				dt[i][j+1] = min(dt[i][j+1], dt[i][j] + (j+1 != B)*a[i+j+1-B]);
			}
		}
	}
	printf("%d\n",dt[n*m][B]);
	track(n*m, B);
	if(f) swap(n, m);
	for(int i=1;i<=m;i++) {
		for(int j=1;j<=n;j++) {
			printf("%d ",ans[n*(i-1)+j]);
		}
		puts("");
	}
}

Compilation message

testdata.cpp: In function 'int main()':
testdata.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
testdata.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct
2 Correct 2 ms 504 KB Correct
3 Correct 2 ms 988 KB Correct
4 Correct 10 ms 6376 KB Correct
5 Correct 152 ms 54316 KB Correct
6 Correct 957 ms 215228 KB Correct
7 Correct 975 ms 215672 KB Correct
8 Correct 4 ms 215672 KB Correct
9 Correct 4 ms 215672 KB Correct
10 Correct 2 ms 215672 KB Correct
11 Correct 3 ms 215672 KB Correct
12 Correct 5 ms 215672 KB Correct
13 Correct 4 ms 215672 KB Correct
14 Correct 11 ms 215672 KB Correct
15 Correct 29 ms 215672 KB Correct
16 Correct 77 ms 215672 KB Correct
17 Correct 319 ms 215672 KB Correct
18 Correct 888 ms 215672 KB Correct
19 Correct 31 ms 215672 KB Correct
20 Correct 644 ms 215672 KB Correct
21 Correct 461 ms 215672 KB Correct
22 Correct 191 ms 215672 KB Correct
23 Correct 300 ms 215672 KB Correct
24 Correct 941 ms 215672 KB Correct
25 Correct 962 ms 217728 KB Correct