oj.uz

Submission #28559

# Submission time Handle Problem Language Result Execution time Memory
28559 2017-07-16T07:22:00 Z AcornCkiGuiziTeam(#1202, dotorya, cki86201, zigui) Test Data Creation (FXCUP2_testdata) C++14
1 / 1
 1553 ms 213864 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 213864 KB Correct
2 Correct 13 ms 213864 KB Correct
3 Correct 6 ms 213864 KB Correct
4 Correct 13 ms 213864 KB Correct
5 Correct 186 ms 213864 KB Correct
6 Correct 1406 ms 213864 KB Correct
7 Correct 1553 ms 213864 KB Correct
8 Correct 13 ms 213864 KB Correct
9 Correct 29 ms 213864 KB Correct
10 Correct 26 ms 213864 KB Correct
11 Correct 16 ms 213864 KB Correct
12 Correct 16 ms 213864 KB Correct
13 Correct 13 ms 213864 KB Correct
14 Correct 16 ms 213864 KB Correct
15 Correct 36 ms 213864 KB Correct
16 Correct 83 ms 213864 KB Correct
17 Correct 316 ms 213864 KB Correct
18 Correct 1413 ms 213864 KB Correct
19 Correct 33 ms 213864 KB Correct
20 Correct 763 ms 213864 KB Correct
21 Correct 519 ms 213864 KB Correct
22 Correct 163 ms 213864 KB Correct
23 Correct 323 ms 213864 KB Correct
24 Correct 1413 ms 213864 KB Correct
25 Correct 1446 ms 213864 KB Correct