oj.uz

Submission #28498

# Submission time Handle Problem Language Result Execution time Memory
28498 2017-07-16T06:43:15 Z Shocking Hot(#1200, khsoo01) Test Data Creation (FXCUP2_testdata) C++14
1 / 1
 1069 ms 215420 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:21: 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:20: 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 0 ms 215420 KB Correct
2 Correct 0 ms 215420 KB Correct
3 Correct 0 ms 215420 KB Correct
4 Correct 6 ms 215420 KB Correct
5 Correct 129 ms 215420 KB Correct
6 Correct 1039 ms 215420 KB Correct
7 Correct 1049 ms 215420 KB Correct
8 Correct 0 ms 215420 KB Correct
9 Correct 0 ms 215420 KB Correct
10 Correct 0 ms 215420 KB Correct
11 Correct 0 ms 215420 KB Correct
12 Correct 3 ms 215420 KB Correct
13 Correct 0 ms 215420 KB Correct
14 Correct 6 ms 215420 KB Correct
15 Correct 19 ms 215420 KB Correct
16 Correct 63 ms 215420 KB Correct
17 Correct 346 ms 215420 KB Correct
18 Correct 949 ms 215420 KB Correct
19 Correct 26 ms 215420 KB Correct
20 Correct 706 ms 215420 KB Correct
21 Correct 493 ms 215420 KB Correct
22 Correct 173 ms 215420 KB Correct
23 Correct 299 ms 215420 KB Correct
24 Correct 1002 ms 215420 KB Correct
25 Correct 1069 ms 215420 KB Correct