Submission #28559

#	Time	Username	Problem	Language	Result	Execution time	Memory
28559		AcornCkiGuiziTeam (#68)	Test Data Creation (FXCUP2_testdata)	C++14	1 / 1	1553 ms	213864 KiB

testdata

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:1048576")  
using namespace std;

#define mp make_pair  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef tuple <int, int, int> t3;

int IT_MAX = 1 << 17;
const ll MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)

int in[90050];
int dp[90050][601];
int N, M;
int aa(int a, int b) {
	if (a == 0 && b == 0) return in[0];

	int t = a - b + 300;
	if (dp[a][t] >= 0) {
		int rv = dp[a][t];
		if (a == b) rv /= 4;
		else rv /= 2;
		return rv;
	}

	int x1 = a / N, y1 = a%N, x2 = b / M, y2 = b%M;
	int rv = INF;
	if (a > b) {
		if (x1) rv = min(rv, (aa(a - N, b) + in[a]) * 2);
		if (y1) rv = min(rv, (aa(a - 1, b) + in[a]) * 2 + 1);
	}
	else if (a < b) {
		if (x2) rv = min(rv, (aa(a, b - M) + in[b]) * 2);
		if (y2) rv = min(rv, (aa(a, b - 1) + in[b]) * 2 + 1);
	}
	else {
		if (x1 && x2) rv = min(rv, (aa(a - N, b - M) + in[a]) * 4);
		if (x1 && y2) rv = min(rv, (aa(a - N, b - 1) + in[a]) * 4 + 1);
		if (y1 && x2) rv = min(rv, (aa(a - 1, b - M) + in[a]) * 4 + 2);
		if (y1 && y2) rv = min(rv, (aa(a - 1, b - 1) + in[a]) * 4 + 3);
	}
	dp[a][t] = rv;
	if (a == b) rv /= 4;
	else rv /= 2;
	return rv;
}

bool chk[90050];
int main() {
	int i, j;
	scanf("%d %d", &M, &N);
	for (i = 0; i < N*M; i++) scanf("%d", &in[i]);

	memset(dp, 0xff, sizeof(dp));
	printf("%d\n", aa(N*M - 1, N*M - 1));

	int x = N*M - 1, y = N*M - 1;
	while (x != 0 || y != 0) {
		int nx = x, ny = y;
		int t = x - y + 300;
		chk[max(x, y)] = true;
		if(x > y) {
			if (dp[x][t] % 2 == 0) nx = x - N;
			else nx = x - 1;
		}
		else if(x < y) {
			if (dp[x][t] % 2 == 0) ny = y - M;
			else ny = y - 1;
		}
		else {
			if (dp[x][t] % 4 == 0) nx = x - N, ny = y - M;
			else if (dp[x][t] % 4 == 1) nx = x - N, ny = y - 1;
			else if (dp[x][t] % 4 == 2) nx = x - 1, ny = y - M;
			else nx = x - 1, ny = y - 1;
		}
		x = nx, y = ny;
	}
	chk[0] = 1;
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) printf("%d ", (int)chk[i*M+j]);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

testdata.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
testdata.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1048576")  
 ^
testdata.cpp: In function 'int main()':
testdata.cpp:89:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N);
                        ^
testdata.cpp:90:47: 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", &in[i]);
                                               ^

• Subtask 1: 1 / 1